## Recursion for Project Euler

Today, we continue our excursion into programming motivated by Project Euler. Here's the second problem:

#### Project Euler question 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: $$1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \ldots$$ By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

This particular problem gives us a nice opportunity to talk about recursion and iteration. Generally, the first is quite elegant but the second is more efficient.

## The Fibonacci numbers

The Fibonacci numbers have a lovely recursive defintion: $$ F_n = \begin{cases} n & \text{if } n=0 \text{ or } n=1 \\ F_{n-1}+F_{n-2} & \text{if } n>1. \end{cases} $$

Here's some naive code that translates that recursion directly to Python.

Unfortunately, this code runs sooo slow - even a number as small as 100 is beyond reach. To see why, let's implement a counter that keeps track of how many times the function calls itself.

Can you see why this is happening? To help, try running the code with `fibr(n)`

for several small values of `n`

.

There is a standard technique, called memoization, that gets around this issue by storing values that have already been computed. We can implement this like so:

To see what happened, try adding `memoize.cache`

inside the `print`

function.

## Project Euler Solution

With that stuff in hand, we can now determine a solution to the Project Euler question.

### Problem 1

Let the sequence be defined by the recurrenceFind the sum of all the numbers less than that are divisble by .

To submit your solution, you should respond to my email with subject line "Problems Lab 2 #1". Be sure to include the Sage Cell Server's Short link to the Python code that you wrote to generate your solution.

## Closed form

Here's an amazing closed form expression for the $n^{\text{th}}$ Fibonacci number: $$ F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}, $$ where $\phi = (1+\sqrt{5})/2$ is the Golden Ratio and $\psi = -1/\phi = (1-\sqrt{5})/2$.

One way to see why this works is as follows. The constants $\phi$ and $\psi$ are exactly the roots of $x^2-x-1$. Solving for $x^2$ and multiplying by $x^n$, we see that any root of that quadratic satisfies, $$x^{n+2} = x^{n+1} + x^n.$$ That is, the sequences $\phi^n$ and $\psi^n$ both satisfy the Fibonacci recurrence. As a result, so does any linear combination $a\phi^n + b\psi^n$. If we can just choose $a$ and $b$ so that $$ \begin{align} a \phi^0 + b \psi^0 &= 0 \\ a \phi^1 + b \psi^1 &= 1 \\ \end{align}, $$ then we must also have $a \phi^n + b \psi^n = F_n$ for all $n$!

We can automate the process of finding $a$ and $b$ using Sage and then checking that it works as follows:

### Problem 2

Implement a closed form expression for the numbers and compute the first ten of them.

To submit your solution, you should respond to my email with subject line "Problems Lab 2 #2". Be sure to include the Sage Cell Server's Short link to the Python code that you wrote to generate your solution.