Recursion

Recursion is the process of defining something in terms of itself.

Example of Recursion

If you thought loops were the only way to iterate over a list, you were wrong! Recursion is fundamental to functional programming because it's how we iterate over lists while avoiding stateful loops. Take a look at this function that sums the numbers in a list:

def sum_nums(nums):
    if len(nums) == 0:
        return 0
    return nums[0] + sum_nums(nums[1:])

print(sum_nums([1, 2, 3, 4, 5]))
# 15

1. Solve a Small Problem

Our goal is to sum all the numbers in a list, but we're not allowed to loop. So, we start by solving the smallest possible problem: summing the first number in the list with the rest of the list:

return nums[0] + sum_nums(nums[1:])

2. Recurse

So, what actually happens when we call sum_nums(nums[1:])? Well, we're just calling sum_nums with a smaller list! In the first call, the nums input was [1, 2, 3, 4, 5], but in the next call it's just [2, 3, 4, 5]. We just keep calling sum_nums with smaller and smaller lists.

3. The Base Case

So what happens when we get to the "end"? sum_nums(nums[1:]) is called, but nums[1:] is an empty list because we ran out of numbers. We need to write a base case to stop the madness.

if len(nums) == 0:
    return 0

The "base case" of a recursive function is the part of the function that does not call itself.

Assignment

Doc2Doc can automatically generate various layouts for a page. There are a lot of possible layouts, so we need a factorial function to calculate the total number of possible layouts.

A factorial is the product of all positive integers less than or equal to a number. For example, 5! (read: "five factorial") is 5 * 4 * 3 * 2 * 1, which is 120.

Complete the factorial_r function. It should recursively calculate the factorial of a number.

Tips

1. What's a small problem you can solve first?

2. How can you go from the "first" value of x to the "next" value of x, all the way down to the "last" value of x?

3. What's the base case that should stop the recursion?

4. Since 0! is an empty product, what should an input of 0 return?

def factorial_r(x):
    pass

Solution

def factorial_r(x):
    if x == 0:    # Base Case
        return 1
    return (x * factorial_r(x-1))    # Recursive Case

How Factorial Works

The factorial of a number n (denoted as n!) is:

$$n!=n×(n−1)×(n−2)×...×1$$

For example:

• 5! = 5 × 4 × 3 × 2 × 1 = 120

• 4! = 4 × 3 × 2 × 1 = 24

• 3! = 3 × 2 × 1 = 6

• 1! = 1

• 0! is defined as 1 (base case)

Step-by-Step Execution

Let's go through an example: factorial_r(3)

1. factorial_r(3)

   • x is not 0, so it returns 3 * factorial_r(2)

2. factorial_r(2)

   • x is not 0, so it returns 2 * factorial_r(1)

3. factorial_r(1)

   • x is not 0, so it returns 1 * factorial_r(0)

4. factorial_r(0)

   • x == 0, so it returns 1 (base case)

Now, let's resolve the function calls:

factorial_r(1) = 1 * 1 = 1
factorial_r(2) = 2 * 1 = 2
factorial_r(3) = 3 * 2 = 6

Key Concepts

• Base Case (x == 0) Prevents infinite recursion and stops the function when x reaches 0.

• Recursive Case (x * factorial_r(x - 1)) Keeps calling itself with a smaller number until it reaches the base case.