Recursive Functions ​

Inside a function, it is possible to call other functions. If a function calls itself internally, it is known as a recursive function.

For example, let’s calculate the factorial ( n! = 1 \times 2 \times 3 \times \ldots \times n ), represented by the function fact(n). It can be seen that:

fact(n)=n!=1×2×3×⋅⋅⋅×(n−1)×n=(n−1)!×n=fact(n−1)×n

Thus, fact(n) can be represented as ( n \times \text{fact}(n-1) ), with a special case handling when ( n = 1 ).

The recursive implementation of fact(n) is as follows:

def fact(n):
    if n == 1:
        return 1
    return n * fact(n - 1)

This is a recursive function. You can test it out:

>>> fact(1)
1
>>> fact(5)
120
>>> fact(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

If we compute fact(5), we can observe the calculation process as follows:

=> fact(5)
=> 5 * fact(4)
=> 5 * (4 * fact(3))
=> 5 * (4 * (3 * fact(2)))
=> 5 * (4 * (3 * (2 * fact(1))))
=> 5 * (4 * (3 * (2 * 1)))
=> 5 * (4 * (3 * 2))
=> 5 * (4 * 6)
=> 5 * 24
=> 120

The advantage of recursive functions is their simplicity and clear logic. In theory, all recursive functions can be rewritten as loops, but loops may not be as straightforward as recursion.

When using recursion, it's essential to prevent stack overflow. In a computer, function calls are implemented using a stack data structure, where each function call adds a stack frame, and each return removes one. Since stack size is limited, too many recursive calls can lead to a stack overflow. Try computing fact(1000):

>>> fact(1000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in fact
  ...
  File "<stdin>", line 4, in fact
RuntimeError: maximum recursion depth exceeded in comparison

The solution to stack overflow issues with recursion is tail recursion optimization. Essentially, tail recursion and looping have the same effect, and looping can be considered a special case of tail recursion.

Tail recursion occurs when a function calls itself and returns the result of that call directly, without any further computation. This allows the compiler or interpreter to optimize the recursion so that no matter how many calls are made, only one stack frame is used, preventing stack overflow.

The previous fact(n) function isn't tail-recursive because of the multiplication expression return n * fact(n - 1). To convert it to a tail-recursive version, we need to pass the accumulated result through each recursive call:

def fact(n):
    return fact_iter(n, 1)

def fact_iter(num, product):
    if num == 1:
        return product
    return fact_iter(num - 1, num * product)

In this version, return fact_iter(num - 1, num * product) only returns the recursive function itself. The expressions num - 1 and num * product are computed before the function call, so they do not affect the call.

The invocation of fact_iter(5, 1) proceeds as follows:

=> fact_iter(5, 1)
=> fact_iter(4, 5)
=> fact_iter(3, 20)
=> fact_iter(2, 60)
=> fact_iter(1, 120)
=> 120

If tail call optimization is applied, the stack will not grow, and no matter how many calls are made, it will not result in a stack overflow.

Unfortunately, most programming languages do not optimize for tail recursion, and the Python interpreter does not either, meaning that even if you modify the fact(n) function to be tail-recursive, a stack overflow may still occur.

Exercise ​

The Tower of Hanoi can be implemented easily with recursion.

Write the move(n, a, b, c) function, which accepts the parameter n, representing the number of disks on the first rod, A. The goal is to print the method to move all the disks from rod A to rod C, using rod B as an auxiliary:

def move(n, a, b, c):
    if n == 1:
        print(a, '-->', c)

Expected output:

A --> C
A --> B
C --> B
A --> C
B --> A
B --> C
A --> C

Test it with:

move(3, 'A', 'B', 'C')

Summary ​

The advantage of using recursive functions is their simple and clear logic. The drawback is that deep recursion can lead to stack overflow.

Languages with tail recursion optimization can prevent stack overflow by using tail recursion. In fact, tail recursion and looping are equivalent, and programming languages without loop constructs must use tail recursion to implement loops.

The standard Python interpreter does not optimize tail recursion, so any recursive function may cause a stack overflow.