Table of Contents

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. ⤴