Exercise 8.4

Question 1

Write a function that calculates the \(n\)-th term of the recursive sequence:

\[ T_n = 2\times T_{n-1} + 1 ~~~~ ,n > 0 \]

where \(T_0\) is provided as an argument in the function.

Don’t use loops or list comprehension.

Question 2

Write a function to calculate the sum:

\[ \sum_{i = 1}^{n} i = 1 + 2 + \dots + n \]

where \(n\) is the function argument.

Don’t use loops or list comprehension, or the closed form solution to the series.

Question 3 - Bonus

Second order recursion is a bit more tricky to pull of efficiently with recursive functions. Write a function to calculate the \(n\)-th term of the Fibonnaci series:

\[\begin{align*} T_0 &= 1 \\ T_1 &= 1 \\ T_n &= T_{n-1} + T_{n-2}\\ \end{align*}\]

where \(n\) is an argument of the function. Don’t use loops, only function recursion.

Are you making any repeated calculations? Try to come up with a solution that avoids this.