Recursive Functions

Recursive Functions#

Midjourney: Fractal

History repeats itself, first as tragedy, second as farce.

— Karl Marx

Slides/PDF#

Recursive functions are functions that call themselves. Recursion (from Latin recurrere ‘to run back’) refers to an infinite process that contains itself as part or that can be defined using itself.

Recursion is used particularly in divide-and-conquer algorithms or in combinatorial problems.

To define a recursive function in Python, we only need a function that calls itself.

def recursive_function():
	# Statement
	recursive_function() # We call ourselves again (as a function) once more

For example, recursive functions can be used to implement loops.

def while_loop(n):  # n as the maximum recursion depth
	if n > 0:
		print(f"Die Funktion wird rekursiv ausgeführt bis die Bedingung am Anfang der Schleife {n} > 0 wahr ist")
		while_loop(n - 1)  # we decrement the variable n

The recursive function is executed three times because the condition is true and we count down to zero. Just like with the while loop.

while_loop(3)

Die Funktion wird rekursiv ausgeführt bis die Bedingung am Anfang der Schleife 3 > 0 wahr ist
Die Funktion wird rekursiv ausgeführt bis die Bedingung am Anfang der Schleife 2 > 0 wahr ist
Die Funktion wird rekursiv ausgeführt bis die Bedingung am Anfang der Schleife 1 > 0 wahr ist

Thus it becomes evident that loops can always be implemented by recursion—something used by functional programming languages, which only know functions.

Example of a Recursive Function - Factorial#

The standard example of a recursive function is the calculation of the factorial of a number. It is defined as the product of the natural numbers from 1 to \(n\).

\(n! = 1 \cdot 2 \cdot 3 \cdots n = \prod_{k=1}^n k\)

def factorial_recursive(x):
    if x > 1:
        return x * factorial_recursive(x-1)
    else:
        return 1

The factorial of the number 10 is defined as:

10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

3628800

which is identical to the output of our function

factorial_recursiv(10)

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[6], line 1
----> 1 factorial_recursiv(10)

NameError: name 'factorial_recursiv' is not defined

When we call the function, it calls itself recursively and counts down from x=10 to 1. Each function call can be viewed as a pair of parentheses, so that, in the end, the following calculation is performed, which matches the calculation above.

10 * (9 * (8 * (7 * (6 * (5 * (4 * (3 * (2 * (1)))))))))

3628800

This simple example can also be implemented using a loop.

def factorial_loop(x):
    result = x
    index = x - 1
    while index > 1:
        result *= index
        index -= 1
    return result

factorial_loop(10)

3628800

This is usually more performant, as functions generally take a bit longer to execute, since they have their own local variable scope and run on the stack (see the next section).

We’ll perform a runtime comparison once using the timeit function in the Jupyter Notebook. It calls the function several times and computes the average execution time.

%timeit factorial_recursive(1000)

177 μs ± 1.27 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

%timeit factorial_loop(1000)

170 μs ± 712 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

We see that the loop-based variant is somewhat faster than the recursive variant.

However, recursive functions are usually more readable and cannot always be expressed with loops, for example when several variables are manipulated.

Infinite Recursion, Stack and Heap#

Warning

Since recursive functions conceptually resemble loops, the same problem of infinite recursion arises here as well. As with while loops, recursive functions can theoretically diverge indefinitely!

Therefore at least one path in the function must not be recursive.

Practically, however, endless recursion leads to stack overflow errors. This happens because Python has to keep track of which function called which other function in order to return to the correct function and position when it finishes. This is done via a list called the Stack.

The Stack is a LIFO list (Last In First Out) where the last element added (the newly called function) must also be the first one removed (when the newly called function ends). It’s basically like a stack of books. The Stack grows so large with endless recursion that it no longer fits in the allocated memory, which is the stack overflow error.

By the way, the variables are not stored on the Stack, but reside in the Heap. The Heap, in comparison to the Stack, can grow as large as the available memory and more closely resembles a FIFO list (First In, First Out), since memory from old variables that are no longer valid is freed.

A stack overflow error is a critical programming error that cannot be caught, but always leads to the termination of the program. As an example, we invoke our first-defined recursive function and see the error message from the Python kernel crash.

# If we run the following function, we will receive the error message below

#recursive_function()

Canceled future for execute_request message before replies were done

The kernel has crashed while executing code in the current cell or a previous cell. Please check the code in the cell(s) to identify a possible cause of the error. Click here to obtain more information. For more details, see the Jupyter log.

Contents