Recursions — Python: Functions

• Recursions as termination conditions
• Stack overflows
• Types of recursion

To understand recursion, one must first understand recursion. Recursion in programming is an opportunity to define a function using its definition.

Mathematics defines it this way, which is why most programming languages adopt this approach. Python is no exception here: usually, you can only use definitions given earlier in the function body. But there is one exception, a function can call itself in its body. It looks like this:

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

https://replit.com/@hexlet/Python-functions-recursion-factorial#main.py

This function calculates the factorial of the number n by multiplying the number by the factorial of the number n - 1.

Recursions as termination conditions

The example demonstrates a condition that terminates the recursion. The first call to this function will cause the program to loop if you remove it in this function that checks that the argument is not negative. The function will continue to call itself again and again.

There is almost always a similar condition in the definitions of recursive functions. It allows the calculation to go along one of two branches:

• Either recursive, where the function calls itself sometimes multiple times
• Or terminal, which will terminate the function and return the result

There is a rule — some of the arguments of a recursive function must always decrease.

Decreasing can mean lowering the counter, dropping the head of the list when moving to its tail, or the function calling itself part of the original structure when processing tree-like data structures.

Unfortunately, it is generally only possible to tell that a program will not loop by staring at it and using tests. It is essential to check that the recursion termination condition gets triggered.

Stack overflows

In most programs written in languages that support function calls, this very call goes as follows:

• The program stores the current place in the stack before calling the function
• It discards the corresponding stack element when the function returns the result

A stack is an abstract data type similar to stacks of coins. We place coins the way we will remove the last one first. In other words, we add and remove them in the opposite order. The values of the function arguments, and sometimes service information, are stored in the same stack.

However, the memory allocated to the stack at program startup is finite. What happens if the function calls itself and does not return the result? This memory will run out at some point. When the memory allocated for the call stack runs out, a stack overflow happens.

It means you cannot calculate the factorial for sufficiently large numbers using a recursive function. But you can calculate it using an iterative function written using loops and variables.

By the way, this is what stack overflow looks like when calculating a factorial:

factorial(1000)
# From the traceback, the most recent calls are the last:
#   File "<stdin>", line 1, in <module>
#   File "<stdin>", line 4, in factorial
#   File "<stdin>", line 4, in factorial
#   File "<stdin>", line 4, in factorial
#   [The previous line repeated 995 more times]
#   File "<stdin>", line 2, in factorial
# RecursionError: maximum recursion depth exceeded in comparison

The message says that the maximum recursion depth has been exceeded.

Recursion depth is the number of consecutive calls a function makes to itself without returning a value. In Python, the maximum length is artificially limited because it is easier to count the number of calls than to predict when memory runs out.

You might wonder why programmers do not stop using recursive functions and switch to iterative ones. We can implement some algorithms easier if you use recursion rather than loops. Often, these algorithms work with recursive data structures — trees, dictionaries, dictionaries of dictionaries, etc.

When implementing these algorithms, you should remember that stack memory is not infinite. However, the data structures we process are usually finite, so you should not abandon recursion.

Types of recursion

There are several types of recursion:

• Direct recursion when the function calls itself directly
• Indirect recursion when the first function calls the second one inside itself, which will at some point call the first one

If, when calculating the result of a function, it needs to call itself once, as in the example with factorial, then we observe a linear recursion. Nothing about the total number of function calls in the body. We are only talking about the number of calls whose results we need for one overall calculation.

Let us consider two different examples: in one, the recursion will be linear, and in the other, it will be cascading. It is what they call recursion when a function calls itself multiple times. The recursion in this function tests the Collatz Conjecture, and it is linear:

def collatz(n):
    if n == 1:
        return True
    if n % 2 == 0:
        return collatz(n // 2)
    return collatz(n * 3 + 1)

https://replit.com/@hexlet/Python-functions-recursion-collatz#main.py

We see two recursive calls in the function body, but we use only one in each specific call. The recursive function below calculates the next Fibonacci Number, and it cascades:

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

https://replit.com/@hexlet/Python-functions-recursion-fibonacci#main.py

Here, the function always calls itself twice. First, there will be two calls to itself, which will turn into four (2 calls times 2), then into eight. The number of calls grows exponentially, hence why the recursion cascades.

Recursion is a powerful tool in the right hands. We can solve many tasks by using recursion skillfully and elegantly.