Recursion¶

It is possible for a function to call itself. The act of a function calling itself is called recursion, and a function that uses recursion is referred to as recursive. It might not be immediately obviously what would happen if a function was to call itself, or why this might be useful. In fact, recursions can be a difficult concept to fully understand, but it is none-the-less a very powerful tool for addressing certain types of problems. In this lesson we will discuss how recursion work. We will also provide an indication as to some of the potential uses of recursion.

First Example of Recursion¶

In the cell below, we create a function named countdown(). Notice that this function calls itself, and is thus recursive.

def countdown(n):
    if n <= 0:
        print('Blastoff!')
    else:
        print(n)
        countdown(n-1)

We will now call the function, supplying a value of 5 for the parameter n.

countdown(5)

5
4
3
2
1
Blastoff!

Let’s break down what occurred when we called countdown() in the previous cell.

We explicitly called countdown(5). The if condition did not trigger, so 5 was printed, and then countdown(4) was called.
Within the call countdown(4), the if condition did not trigger, so 4 was printed, and then countdown(3) was called.
Within the call countdown(3), the if condition did not trigger, so 3 was printed, and then countdown(2) was called.
Within the call countdown(2), the if condition did not trigger, so 2 was printed, and then countdown(1) was called.
Within the call countdown(1), the if condition did not trigger, so 1 was printed, and then countdown(0) was called.
Within the call countdown(0), the if condition triggered, printing 'Blastoff!'. No other functions were called, allowing the recursion to end.

Each new call to countdown() creates its own local scope that lives inside the local scope from which it was called. Furthermore, none of the function calls are allowed to exit until of its calls that it has created have finished executing. This is demonstrated more clearly in the following example.

Second Recursion Example¶

In the example below, notice that we have included print statements before and after the line that involves recursion. When a function call encounters a call to a function (even itself), it will pause its own execution, and will then process the new call to completion before moving own to later instructions.

def recursion_example(n):
    print('Beginning call for n =', n)

    if n == 0:
        print('We have hit zero!')
    else:
        recursion_example(n-1)
        
    print('Finishing call for n =', n)

We will now test this function by calling it with n=3.

recursion_example(2)

Beginning call for n = 2
Beginning call for n = 1
Beginning call for n = 0
We have hit zero!
Finishing call for n = 0
Finishing call for n = 1
Finishing call for n = 2

Since the last print statement in the definition of recursion_example() occurs after the recursive step, this line does not execute for ANY of the function calls until the recursion ends. At that point, the function calls end in reverse order and the remaining print statements are executed, again, in reverse order.

The diagram below attempts to further explain what happens when we call recursion_example(2). The actions described below occur in the order in which they are shown, and lines with the same level of horizontal indentation occur within the same call to recursion_example().

Base Case and Infinite Recursion¶

Notice that both of the examples we provided above include an if...else statement in which one branch causes the function to recurse, and the other branch allows the recursion to end. This is typical of recursive functions. A recursive function will generally have one or more sets of parameter values for which the function does not recurse. Such a set of parameter values is referred to as a base case for the function. Recursive functions should be written so as to guarantee that they will always encounter a base case. Otherwise, the function might recur infinitely.

Two examples of potentially infinitely recursive functions are provided below. The first function does nothing other than call itself, and there is no condition to keep it from continuing to do so. The second function had a condition that could potentially allow it to stop recurring, but notice that this condition will never be met if an odd number is supplied for the parameter n.

def to_infinity():
    to_infinity()

def infinite_odds(n):
    print(n)
    if n == 0:
        print('Done!')
    else:
        infinite_odds(n-2)

In truth, Python will not allow infinite recursion. There is a maximum depth at which recursive functions can be stacked. By default, this number is 3000 on most systems. If the number of recursive calls to a function hits this depth, an error message will be displayed saying "maximum recursion depth exceeded".

Applications of Recursion¶

We will now provide examples of a few ways in which recursion can be applied.

Factorial¶

In the cell below, we use recursion to write a function that calculates the factorial of a positive integer.

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

We will now test our factorial() function by calling it on the first 10 positive integers.

for i in range(1, 11):
    print(factorial(i))

Sum Elements¶

Suppose that you are provided with several integers, but that the integers are stored in a collection of nested lists. We will write a recursive function named sum_nested() to calculate the sum of the elements in such a structure.

def sum_nested(x):
    total = 0
    for item in x:
        if type(item) == list:
            total += sum_nested(item)
        else:
            total += item
    return total

We will now test the function on several examples.

print(sum_nested([1, 2, 3]))
print(sum_nested([1, [2], 3]))
print(sum_nested([1, [2], [1, 2, 3]]))
print(sum_nested([1, [2, [5, 6, [4, 9]]], [1, 2, 3]]))

Palindrome Checker¶

The function below accepts a string as an argument, and then checks to see if that string is a palindrome. It accomplishes that using recursion. At each step, the function checks to see if the first and last character are equal. If so, then it calls itself on the substring that omits those two characters. The recursion ends when we arrive at a string with a lenth of 1 or less.

def is_palindrome(text):
    if len(text) <= 1:
        return True
    if text[0] != text[-1]:
        return False
    return is_palindrome(text[1:-1])

We will now test our function on several examples.

print(is_palindrome('abcba'))
print(is_palindrome('abgfcfgba'))
print(is_palindrome('abfgcfgba'))
print(is_palindrome('aaa'))
print(is_palindrome('aa'))
print(is_palindrome('a'))

True
True
False
True
True
True

Python Programming