## Recursion

It’s kinda like magic, but once you get it, it’s pretty cool.
– some 61a student, probably

In essence, a recursive function is a function that calls itself at some point. It’s not special syntax within Python. For those who have prior experience with mathematical induction, it has many similarities.

### Factorial

Let’s take the example of computing a factorial, the product of all positive integers less than or equal to n. 1

A simple way to think about factorial(n) is as follows:

• If $$n \leq 1$$, then $$n! \rightarrow 1$$
• Otherwise, $$n! \rightarrow n * (n-1)!$$

Let’s transform this into Python:

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


Let’s write this to be more Pythonic by dropping the else and deintenting the inner block:

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


This example is recursive! Our base case is the simplest problem, when factorial(n) is a known value. In this case, our base case is when n <= 1. Our recursion is a known reduction of the problem, where factorial(n) is the same problem as the easier problem n * factorial(n-1). This way, we are reducing our problem into smaller and smaller problems until we get to a known state.

### For Those Familiar With Induction

Proof by induction is logically very similar to recursion.

In induction, a typical proof for a mathematical formula goes like:

1. Prove base case
2. Assume the formula holds for $$k$$, and prove that the formula holds for $$k+1$$.

The proof works because:

1. For some base case, we know the formula to be true
2. For some unknown problem of size $$k$$, we have shown the formula to be reduceable to $$k - 1$$.

In recursion, the thinking maps to the above concepts:

1. We want to find a base case that is a known state for some function.
2. For a problem $$k$$ with no immediately known solution, we find a reduction to a size of $$k - 1$$.

## Tree Recursion

Recursion on trees?
– the same 61a student, probably

Contrary to its name, tree recursion isn’t recursion on trees. 2 Instead, it refers to the recursion problems that require multiple calls to a function to break down the recurrence.

### Fibonacci

Let’s take a look at the fibonacci sequence, a sequence of numbers where each number in the sequence is the sum of the two prior to it. More formally,

$F_n = \begin{cases} 1, & n = 0, 1 \\[1ex] F_{n-1} + F_{n-2}, & \text{otherwise} \\[2ex] \end{cases}$

We can transform this definition into code. We have the cases

1. If n == 0 or n == 1, then fibonacci(n) -> 1
2. Otherwise, we want fibonacci(n-1) + fibonacci(n-2)

In code:

def fibonacci(n):
if n == 0 or n == 1:
return 1
return fibonacci(n-1) + fibonacci(n-2)


Note that the major difference between this problem and the prior factorial problem is in the recurrence: Fibonacci requires two calls to fibonacci to solve, whereas factorial requires only 1. If we draw out the calls, it looks like a tree (hence the name tree recursion).

## Tips For Thinking Recursively

Recursion finally makes sense!
– the same 61a student :’)

• In some cases, finding the recurrence relation will be easier. In other cases, defining the base cases will be.
• Recurrence relation:
• Think about what the problem is trying to calculate, and how that can be broken down into smaller versions of the same problem. In other words, if we have some $$f(k)$$, think about how that can be broken down to some other $$f(k’)$$, where $$k’ < k$$
• Base cases:
• Think about what the smallest version of the problem is. In the examples above, it’s the smallest, trivial versions of the problem. This is usually some case like $$f(0)$$, $$f(1)$$, or something similar.

## Footnotes

1. https://en.wikipedia.org/wiki/Factorial

2. Recursion on trees (with tree recursion) is a thing, and we’ll be covering it later.