Find a formula for the number of calls needed to compute F

**1. Most significant digit**

Write a recursive function that returns the first (most significant) digit of a number when written in base 10.

**2. Selecting digits**
Write a function that takes an unsigned number `n` and returns
a number formed by some of the digits of `n`, e.g.:
all digits on even positions / odd positions, all digits with a given property (odd/even/greater than 5, etc.)

Hint: Review the reversal of digits, done in class. Here, you won't use all digits. If you don't reverse, you don't need an accumulator and can directly construct the number using the result of the recursive call.

**3. Changing the base**
Write a function that given a natural number computes the value
resulting from the digits of its decimal representation when interpreted
as a hexadecimal number. Example: f(312) = 3 * 256 + 1 * 16 + 2 = 786

Hint: use the same recursive decomposition, but when reconstructing the number, use the new base (16).

**Limits and approximations**

**4. Function root.**
Write a recursive function that computes a root of a given continuous
function `f` in an interval [a, b] with a given precision using the
bisection method, assuming `f(a)` and `f(b)` have opposite signs.
*How to do it*:

If the interval length does not exceed the required precision for the root (say,
10^{-6}, which can be written 1e-6), we can return as answer any point from the interval (a, b, the midpoint, etc.).

Otherwise, compute `f` in the midpoint of the interval, (a+b)/2.
If f(a) * f((a+b)/2) ≤ 0 (the function changes sign), find the root by calling the function recursively on the left half-interval. Otherwise, there must be a root in the right half [(a+b)/2, b], so recursively find the root in that interval.
*Why this works*

Denote m = (a+b).2. We prove by contradiction that f(a) * f(m) ≤ 0 or f(m) * f(b) ≤ 0 (or both).

If both were > 0, by multiplication we'd get f(a) * f(m)^{2} * f(b) > 0. We divide by f(m)^{2} which must be *strictly* positive, since the entire product is, and we get f(a) * f(b) > 0 contrary to the problem statement that they have opposite signs.

Note that we do not need a zero check for the endpoints nor the midpoint, the reasoning above shows that the chosen checks suffice.

**5. Series** Write functions that compute the value of a given series.

a) Compute the value of 1/1^{2} + 1/2^{2} + ... + 1/n^{2} for some large `n`. Write versions that start to add from each of the ends. What is the difference in writing the recursion? Is there a difference in the result?

b) Write functions that compute the Taylor series for *e ^{x}*,

Hint: pass the sum computed so far as one of the arguments. To avoid wasteful computation, you may also pass the current term as one of the arguments, and compute the next term starting from the current term.

**6. Limit** Write a function that computes with a given precision (say, 1e-6)
the limit of the sequence *x _{n+1} = f(x_{n})*
(assuming it exists), with

Your program should define a suitable

(Later we will learn how a pointer to

A value for which

Use this approach to compute values of infinite terms, such as 1/(a+1/(a+1/(... + 1/a))) or √a+√a+ ...√a (for given values of

Hint: find the function

**7. Fractals**
Write a program, similar to the one done in class, that draws
the Koch curve, as described here.

The curve can be drawn without lifting pen from paper, so there is no need to
issue commands to move the cursor, each segment starts from where the other
left off. Segments have different orientation: the two central of four
subfigures are tilted clockwise and counterclockwise with π/3 with respect
to the orientation of the enclosing larger figure. Thus, a figure will have
size and orientation (angle) as parameters.

**8. Modular exponentiation**
If p is a prime number, and `a` is not divisible by p, the sequence
`a, a ^{2}, a^{3}, ...` eventually reaches 1 when
computed modulo

For example, let p = 7, and a = 4. Then a

Write a function that takes as parameters an unsigned number

Hint: accumulate and pass as arguments the current exponent

**9 ^{*}. Counting change** Write a recursive function that returns the number of ways
in which a natural number can be written as a sum of ones, twos and threes,
irrespective of order.

Example: 5 can be written in 5 ways: 1 + 1 + 1 + 1 + 1 , 1 + 1 + 1 + 2 , 1 + 2 + 2 , 1 + 1 + 3 , and 2 + 3.

Hint: We can either use a value of 3 in the sum or not. The number of combinations will be the sum for both cases. If we use a value of 3, we are left with

Does the function perform wasteful computation ? Generalize for three arbitrary values instead of 1, 2, and 3.