# Recursion

([home](https://github.com/alexhkurz/introduction-to-programming/blob/master/README.md) ... [previous](https://hackmd.io/@alexhkurz/H1o4Mcr6L) ... [next](https://hackmd.io/@alexhkurz/ryiCiDs08))

In the last session we have seen both the mathematical definition of the Fibonacci numbers

\begin{align}
fib(0) & = 0\\
fib(1) & = 1\\
fib(n+2) & = fib(n) + fib(n+1)
\end{align}

as well as an implementation [iterative_fib.py](https://github.com/alexhkurz/introduction-to-programming/blob/master/src/iterative_fib.py):

def fib(n):
fib_one = 0
fib_two = 1
for i in range(0,n+1):
if i == 0:
fib = fib_one
elif i == 1:
fib = fib_two
else:
fib = fib_one + fib_two
fib_one = fib_two
fib_two = fib
return fib

Both the mathematics and the program are two precise definitions of $fib(n)$.

But if you compare the two, the program is more difficult to read. In fact, most of the program consists of what we might call "bookkeeping". The mathematical definition
- simply lists the 3 relevant patterns

and

- does not need if-then-else
- does not need the auxiliary variables `i`, `fib_one`, `fib_two`, `fib`
- does not need assignments

To appreciate the point about assignment, recall how the mathematical equality $=$ is different from assignment `=`:
- Mathematically equality knows nothing about time.
$$fib(n+2) = fib(n) + fib(n+1)$$

defines an "eternal truth" that holds for all natural numbers $n$.
- On the other hand,

fib = fib_one + fib_two

is a command describing how the variable `fib` changes in time when the command is executed.

Wouldn't it be nice if we could just write the mathematical definition in Python and leave it to the machine (or interpreter/compiler more precisely) to generate the necessary computation from it?

## Computing with recursive definitions

We first want to understand whether it is possible at all to turn a mathematical definition such as

\begin{align}
fib(0) & = 0\\
fib(1) & = 1\\
fib(n+2) & = fib(n) + fib(n+1)
\end{align}

into a computation in a principled way that could be automatised.

**Remark:** This style of definition is called **recursive**, because, in order to define $fib(n+2)$ we are *recurring* to the values $fib(n)$ and $fib(n+1)$. This definition looks almost circular, since we define $fib$ in terms of itself. But it is a good definition, because at each step one *recurs* to smaller values. (Note that we read the equations from left to right, rewriting the left-hand side by the right-hand side.) The recursion will terminate when we reach $fib(0)$ and $fib(1)$. (Among the three cases that make up the definition, the first two are called the *base cases* while $fib(n+2) = fib(n) + fib(n+1)$ is called the *inductive case*.)

**Activity:** Compute $fib(6)$ by writing out a sequence of mathematical equations, replacing the $\ldots$ below.
\begin{align}
fib(6) & = fib(4) + fib(5)\\
& = \ldots \\
& = 8
\end{align}

Each step should correspond to either the application of one of the three defining equations of $fib$ or to one of the usual rules of mathematics for addition. [Hint: My computation has 37 steps.]

Why do I want you to write out the complete computation?
- To show you that the equational style of computation you learned in high-school extends to more complicated situations.
- The fact that this gets boring and tedious will make you think about how to mechanise this.
- This example illustrates well the technique known as [term-rewrting](https://en.wikipedia.org/wiki/Rewriting), which is the simplest and most important model universal model of computation.
- One advantage of term-rewriting is that we do not remember any "state": Each term in the chain of equations contains all that is needed to continue the computation to the end.
- A disadvantage is that in most steps we find ourselves copying terms that do not change.

The last point can easily be addressed. As it happens so often, thinking about how to get rid of the boring parts reveals interesting structure:

**Activity:** Draw the computation above in tree form by completing the figure below.

fib(6)
|
+
/ \
fib(4) fib(5)
| |
+ +
/ \ / \
... ...

Note that, as opposed to the equational reasoning, `fib(b)` only appears once in the tree now. On the other hand, the computation now proceeds by going up and down the tree in a particular fashion that is more intricate (it is known as [depth-first traversal](https://en.wikipedia.org/wiki/Depth-first_search)).
## Recursion in Python

Typically, modern programming languages do support writing recursive definitions.

def fib(n):
if n==0:
return 0
elif n==1:
return 1
else:
return fib(n-2)+fib(n-1)

print(fib(6))

**Important:** When the Python interpreter encounter the line `def fib(n):` it will **not** execute the function `fib`. It will just learn the definition of `fib`. Only when the Python interpreter processes the line `print(fib(6))`, the `fib(n)` will be called and executed, with the value `n` being `6`.

**Activity:** Download and run [recursive_fib.py](https://github.com/alexhkurz/introduction-to-programming/blob/master/src/recursive_fib.py). Insert print-statements in various places in the program to help you track the execution for small values of `n`.

While the program above illustrates how recursion works in Python, it also highlights that Python does not have all the features that are needed to implement the mathematical definition in an elegant way.

We will therefore also look quickly at a more mathematical programming language.

## Recursion in Haskell

In Haskell, the following is a program.

fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)

Haskell is quite close to mathematical practice in many ways. One of the main differences are the conventions of how to place parentheses. For example, where in maths we would write $fib(n)$, in Haskell we can simply write `fib n`.

**Activity:** Install the [Haskell platform](https://www.haskell.org/platform/). Download [fib.hs](https://github.com/alexhkurz/introduction-to-programming/blob/master/src/fib.hs). Run the program as follows.

ghci
:load fib.hs
fib 5

## Homework

Write recursive programs in Python and Haskell to compute the value of $f(n)$ where $f$ is the any of the sequences of the [previous homework](https://hackmd.io/@alexhkurz/H1o4Mcr6L#Homework). I reproduce them here for convenience.

- $1, 2, 6, 24, 120,\ldots$
- $0,1,3,7,15,31, \ldots$
- $0,1,2,5,12,29,70, 169, \ldots$

We also had

- $0,1,3,6,10,15,\ldots$
- $0,1,5,14,30,55,\ldots$

## Further Reading

- [GeekforGeeks: Program for Fibonacci numbers](https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/)
- [Haskell Wiki: The Fibonacci sequence](https://wiki.haskell.org/The_Fibonacci_sequence)
- [Full Computation of $fib(6)$](https://hackmd.io/@alexhkurz/HJiulVg0U)