Recursion¶

Definition¶

Recursion is an approach to solve computational problems by calling a function in the body that implements this solution by itself.

Recursion in real life¶

Here is a drawing and a meme that show recursion as something you can encounter on a daily basis, something tangible.

Recursion can also be achieved by standing in front of a mirror with another mirror in your hand. We will then obtain the effect of going into the mirror.

Recursive factorial algorithm¶

The function that calls itself is not a bug, although it might seem so at first. In fact, Python (as well as other programming languages) will remember where it left off executing the a function to start a new call from the beginning. After the second-order a completes, Python will go back to the first and continue with it.

The simplest example from high school is a factorial:

We can write down the definition of factorial in several ways, but the latter two represent fully recursive: what the '!' character means in math is determined by that character. Factorial, to be defined, calls factorial (that is, itself).

A recursive function, in addition to referencing itself, also has a condition that terminates the function and returns the final result. If it wasn't for this postcondition, the recursive function would call itself every time, and we would get an "infinite loop". This is written in quotation marks because it is not a loop as such and has nothing to do with loops we have seen so far.

The final condition for the factorial is that the input argument is equal to 0 or 1, because for these numbers, the factorial is explicitly defined (as shown in the figure below).

Simple recursive factorial implementation¶

An example of a factorial implementation code is shown below.

def factorial(n):
    """Calculates factorial.

    Args:
        n: Natural number as input for the algorithm.
    Returns:
        factorial of number n.
    """
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n-1)

Two elements are important here. The final condition:

    if n == 0 or n == 1:
        return 1

and calling the function by itself:

    return n * factorial(n-1)

How is it possible that this approach works?

How does it work?¶

Here's how a recursive algorithm works using the example of implementing factorial:

1. A recursive function is called with an argument 5 - factorial(5).
2. The function checks whether 5 == 0 or 5 == 1, this is not true, so the final result is unknown - it needs to be calculated.
3. The function runs until it calls itself: return n * factorial(n-1).
4. Python remembers that it was working on a solution for a function a while before factorial from n = 5, now, according to the code, it will call the function factorial(4) (5-1=4).
5. Exactly the same will happen with factorial(4), factorial(3), factorial(2), factorial(1) - each time the sequence of recursive calls will increase, Python will remember the order in which the function was run with each argument.
6. For n=1 function factorial knows the solution because it is given in the definition. So it returns a result, so that each previous function can find its own solution and return it to the function "higher", as shown in the block on the right.
7. Finally, the full and ready result goes to the function launched by the user, i.e. factorial(5).

It is extremely important that Python must use new ones with each call and occupy new memory cells - it must store the current result somewhere and remember where the function was called, which called the previous function recursively, etc.

Comparison of recursive and iterative approaches¶

Below is a compilation of two approaches to solving the same problem:

• recursive,
• iterative.

def factorial_rec(n):
    """Calculates the factorial in a recursive way.

    Args:
        n: Natural number as input for the algorithm.
    Returns:
        factorial of numbers n.
    """
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n-1)

def factorial_iter(n):
    """Calculates the factorial in an iterative way.

    Args:
        n: Natural number as input for the algorithm.
    Returns:
        factorial of numbers n.
    """
    result = 1
    for i in range(1, n+1):
        result *= i
    return result

When solving computational problems, usually both paths mentioned above can be taken. The advantage of the recursive approach is often shorter writing and clearer code. An iterative solution is usually faster because the interpreter does not have to "jump" between calls of the same function.

Infinite "loops" in recursive functions¶

ATTENTION! It is extremely important to remember that recursion is not only about self-induction. It is also necessary to provide a final condition. Without it, Python won't know when to stop calling the same function again. There must be a certain set of arguments for which the algorithm concludes that it already has a solution ready and does not need to recursively compute it. Consider the example below.

What happens when the user runs inf_recursion with an argument of 0? The condition in the if statement is not met, so zero will be returned. Nothing bad happened. The problems start when we call inf_recursion with a nonzero argument.

When invoked with the "wrong" argument...

What happened here? The code kept calling new inf_recursion functions recursively. It happened so long that the Python interpreter began to suspect that we might not really want it. The problem with recursion is that in this case we are taking up more and more memory to remember previous function calls. Python breaks this "vicious circle" and raises a RecursionError exception. This means that the limit of consecutive calls has been exceeded.

You can broaden or narrow the recursion "depth" limit.

Please note that we cannot set the limit to just any number. Especially in the example above, the operating system is most likely to block this depth.

Dynamic programming¶

The biggest problem with recursive algorithms is their resource consumption. Can this be prevented? A number of improvements have been proposed, and the algorithms implementing them are classified as dynamic programming.

The dynamic approach assumes:

• creating a recursive solution,
• creating a structure remembering solutions corresponding to the final values,
• using the above structure in the operation of the algorithm - the solution for specific input data after the algorithm is executed is saved in the structure and ready for late return without the need for counting again.

Dynamic programming - example¶

The factorial code in a dynamic approach might look like the following listing:

def factorial(n, memory={0:1, 1:1}):
    """Calculates the factorial using dynamic programming.

    Args:
        n: Natural number as input for the algorithm.
        memory: the dictionary that remembers the results will be updated with each function call.
    Returns:
        factorial of numbers n.
    """
    if n in memory:
        return memory[n]
    else:
        memory[n] = n * factorial(n-1)
        return memory[n]

The most important difference compared to the usual recursive algorithm is the appearance of a structure that remembers the results of previous calls, here called memory.

If the user calls the function factorial (10), the result will be computed and then written into the memory dictionary. On the next call to factorial (11), instead of calculating everything from beginning, the result of the equation will be returned 11*, so that the function will finish its execution faster. You can also "jump over" the depth limit set by the interpreter this way.