2.1 Recursion

A recursive function is a function that calls itself in its body, either directly or indirectly. Recursive functions have three important components:

1. Base case(s), the simplest possible form of the problem you're trying to solve.
2. Recursive case(s), where the function calls itself with a simpler argument as part of the computation.
3. Using the recursive calls to solve the full problem.

Let's look at the canonical example, factorial.

Factorial, denoted with the ! operator, is defined as:

n! = n * (n-1) * ... * 1

For example, 5! = 5 * 4 * 3 * 2 * 1 = 120.

The recursive implementation for factorial is as follows:

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

We know from its definition that 0! is 1. Since n == 0 is the smallest number we can compute the factorial of, we use it as our base case. The recursive step also follows from the definition of factorial, i.e., n! = n * (n-1)!.

The next few questions in lab will have you writing recursive functions. Here are some general tips:

• Paradoxically, to write a recursive function, you must assume that the function is fully functional before you finish writing it; this is called the recursive leap of faith.
• Consider how you can solve the current problem using the solution to a simpler version of the problem. The amount of work done in a recursive function can be deceptively little: remember to take the leap of faith and trust the recursion to solve the slightly smaller problem without worrying about how.
• Think about what the answer would be in the simplest possible case(s). These will be your base cases - the stopping points for your recursive calls. Make sure to consider the possibility that you're missing base cases (this is a common way recursive solutions fail).
• It may help to write an iterative version first.