Link Search Menu Expand Document
The Python Book

Recursion with functions

Recursion is a concept in programming where a function calls itself a finite number of times. This allows us to solve problems that can be broken down into smaller subproblems, similar to the original problem.

An example is the calculation of the factorial n!. This operation consists of multiplying a number by all the previous ones. The factorial 4! is 4*3*2*1 = 24. It is a problem that can be solved recursively because:

  • Computing 4! involves computing 3! and multiplying by 4.
  • Computing 3! involves computing 2! and multiplying by 3.
  • Computing 2! involves computing 1! and multiplying by 2.
  • The factorial 1! is always 1.

We can express this in code as follows. As you can see, the factorial function calls itself. On each new call, the value of n is reduced by 1.

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

Any recursive function has two well-identified branches:

  • 🔁 Recursive call: The function calls itself. It is common for the new call to be made by making some modification to the input. In the case of the factorial, n-1.
  • ✋🏼 Return: At some point, the function stops calling itself and returns. This branch is important because if it does not exist, the function could enter an infinite loop.

Although recursion is fine, do not forget that this can also be written in the normal way. The following code calculates the factorial but without recursion.

def factorial(n):
    # non-recursive
    result = 1
    for i in range(2, n+1):
        result *= i
    return result

Another example is to calculate the Fibonacci series. This series calculates the element n by adding the two previous ones, being the first two 0 and 1. As you can see, the next element is the sum of the two previous ones.

# 0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Similar to the factorial, we can calculate the n element as follows.

def fibonacci(n):
    # recursive
    return n if n <= 1 else fibonacci(n-1) + fibonacci(n-2)

And we can also express it non-recursively like this. Again, with loops of all life.

def fibonacci(n):
    # non-recursive
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Another interesting example of recursion is to convert a list of n dimensions into 1 dimension, something known as flatten.

In this case, we have a list with lists inside. The goal is to have a single list without nesting. This example is interesting since it mixes recursion with generators, something we will see later.

def flatten(lst):
    for item in lst:
        yield from flatten(item) if isinstance(item, list) else (item,)

nested_list = [1, [2, [3, 4], 5], 6]
print(list(flatten(nested_list)))
# [1, 2, 3, 4, 5, 6]