# Recursion on integers

## Factorial

Recursion on integers is similar to recursion on sequences. Typically you have a base case — maybe when the integer is 0 or 1 — and the recursive case makes recursive calls to smaller integers than our parameter.

Computing factorials is a typical example. Recall that the factorial of an integer n is the product of all the integers from 1 to n. For example, the factorial of 5 is 120, from 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5.

To compute factorials recursively, we might have our base case being when the parameter value is 1. For the recursive case, we compute the previous factorial — to get the product of the integers up to n − 1 — and then we can multiply that by n to get the next factorial.

```def factorial(n):     if n <= 1:         return 1     else:         prev = factorial(n - 1)         return prev * n ```

## Fibonacci numbers

A more complex example of recursion is Fibonacci numbers. This is an infinite sequence of integers starting with 1 and 1, and where each succeeding number is the sum of the two preceding numbers in the sequence.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Now suppose we want a function that takes some index and is supposed to return the Fibonacci number at that index. For example, given the index 7, we would hope to return 21, since if you go through the sequence indexing from 0, you would find that 21 is at position 7 in the sequence.

We can do this recursively as follows.

```def fib(index):     if index <= 1:         return 1     else:         a = fib(index - 2)         b = fib(index - 1)         return a + b ```

Notice that this is a bit different from our examples so far, because the recursive case actually involves two recursive calls. This will make tracing through what happens quite a bit more complex.

For example, suppose we want to compute `fib(5)`. Here are the steps the computer goes through to compute the value.

1. We begin working on `fib(5)`. Since 5 > 1, we enter the `else`.
2. We must compute `fib(3)`.
1. We begin working on `fib(3)`. Since 3 > 1, we enter the `else`.
2. We must compute `fib(1)`.
1. We begin working on `fib(1)`. Since 1 ≤ 1, we immediately return 1 as our result.
3. The result of `fib(1)`, 1, is stored in `a`. We now must compute `fib(2)`.
1. We begin working on `fib(2)`. Since 2 > 1, we enter the `else`.
2. We must compute `fib(0)`.
1. We begin working on `fib(0)`. Since 0 ≤ 1, we immediately return 1 as our result.
3. The result of `fib(0)`, 1, is stored in `a`. We now must compute `fib(1)`.
1. We begin working on `fib(1)`. Since 1 ≤ 1, we immediately return 1 as our result.
4. The result of , 1, is stored in `b`. We add `a` and `b`, which is 2, and return this as our result.
4. The result of , 2, is stored in `b`. We add `a` and `b`, which is 3, and return this as our result.
3. The result of `fib(3)`, 3, is stored in `a`. We now must compute `fib(4)`.
1. We begin working on `fib(4)`. Since 4 > 1, we enter the `else`.
2. We must compute `fib(2)`.
1. We begin working on `fib(2)`. Since 2 > 1, we enter the `else`.
2. We must compute `fib(0)`.
1. We begin working on `fib(0)`. Since 0 ≤ 1, we immediately return 1 as our result.
3. The result of `fib(0)`, 1, is stored in `a`. We now must compute `fib(1)`.
1. We begin working on `fib(1)`. Since 1 ≤ 1, we immediately return 1 as our result.
4. The result of , 1, is stored in `b`. We add `a` and `b`, which is 2, and return this as our result.
3. The result of `fib(2)`, 2, is stored in `a`. We now must compute `fib(3)`.
1. We begin working on `fib(3)`. Since 3 > 1, we enter the `else`.
2. We must compute `fib(1)`.
1. We begin working on `fib(1)`. Since 1 ≤ 1, we immediately return 1 as our result.
3. The result of `fib(1)`, 1, is stored in `a`. We now must compute `fib(2)`.
1. We begin working on `fib(2)`. Since 2 > 1, we enter the `else`.
2. We must compute `fib(0)`.
1. We begin working on `fib(0)`. Since 0 ≤ 1, we immediately return 1 as our result.
3. The result of `fib(0)`, 1, is stored in `a`. We now must compute `fib(1)`.
1. We begin working on `fib(1)`. Since 1 ≤ 1, we immediately return 1 as our result.
4. The result of , 1, is stored in `b`. We add `a` and `b`, which is 2, and return this as our result.
4. The result of , 2, is stored in `b`. We add `a` and `b`, which is 3, and return this as our result.
4. The result of , 3, is stored in `b`. We add `a` and `b`, which is 5, and return this as our result.
4. The result of , 5, is stored in `b`. We add `a` and `b`, which is 8, and return this as our result.

## Recursion trees

Since the recursion process can get fairly complex, it can be useful to have a diagram of all the recursive calls. A recursion tree accomplishes this: Each node in the tree corresponds to a recursive call, where the nodes connected to it below are recursive calls made by that node.

Here's the recursion tree diagramming what happens in computing `fib(5)`.

As an example, you can see that the node labeled 4 in this tree has two nodes below it, labeled 2 and 3. This is because in computing `fib(4)`, there are two recursive calls, one with an argument of 2 and another with an argument of 3.

Naturally, any base cases have no nodes below them, since there are no recursive calls in a base case. Thus, there is nothing below any node labeled 0 or 1 in the recursion tree.