Recursion

When learning programming, we often deal with tasks in a linear, straightforward manner. But what if we encounter a problem that requires breaking it down into smaller, similar problems? That's where recursion comes in.

In plain English, recursion is when a function calls itself during its execution. This might sound like it would create an endless loop, but if we design our function correctly, it will eventually reach a point where it no longer calls itself.

Let's start with a familiar real-life example before diving into code.

Imagine a Matryoshka doll. Each time you open a doll, there's a smaller one inside, and you keep going until you reach the smallest doll that cannot be opened. This process of opening dolls is a bit like recursion. The larger problem (opening the first doll) is solved by repeatedly solving smaller versions of the same problem (opening the smaller dolls) until you reach a point where the problem can't be reduced any further (the smallest doll).

Now, let's apply this concept to a Python function:

def countdown(n):
    if n <= 0:
        # Base case: we've reached zero or below, so we stop
        print('Blastoff!')
    else:
        # Recursive case: print the current number and countdown from n-1
        print(n)
        countdown(n - 1)

In this function, countdown(5) would print 5, then call countdown(4), which prints 4, then calls countdown(3), and so on, until it reaches countdown(0) which stops the recursion and prints Blastoff!.

Let's test the function:

countdown(5)

This will output:

5
4
3
2
1
Blastoff!

You can see recursion in action, where the problem of counting down from 5 is broken down into counting down from 4, 3, 2, 1, and finally 0.

The key parts of a recursive function are:

Base case: A condition that stops the recursion. Without this, the function would call itself indefinitely, causing an infinite loop. Here, it's n <= 0.

Recursive case: Where the function calls itself, usually with a different argument. Here, it's countdown(n - 1).

Recursion can be a truly fascinating concept to grasp. It's like a magical tool in your programming toolbox, allowing you to break down complex problems into smaller, manageable pieces. Think of it as solving a big puzzle: you start with a complex picture, but as you solve smaller sections one by one, the whole picture begins to reveal itself.

Video preview — A video by Reducible - 5 Simple Steps for Solving Any Recursive Problem

As a demonstration of how one might have a computation inside a recursive function, we can try to calculate the sum of all the numbers from 1 … n given a number n:

def sum(n):
    print(f'sum() called with argument {n}')
    if n == 1:         # In case the given number is 1 => the sum is 1 as well
        return 1       # Return here and don't execute the following commands
    prev = sum(n - 1)  # Compute the sum for 1...(n-1)
    
    print(f'Adding current {n} to prev {prev}')
    return n + prev    # Return n + the sum for 1...(n-1)

print(sum(10))

This will print all the calls and the number 55 at the end:

sum() called with argument 10
sum() called with argument 9
sum() called with argument 8
sum() called with argument 7
sum() called with argument 6
sum() called with argument 5
sum() called with argument 4
sum() called with argument 3
sum() called with argument 2
sum() called with argument 1
Adding current 2 to prev 1
Adding current 3 to prev 3
Adding current 4 to prev 6
Adding current 5 to prev 10
Adding current 6 to prev 15
Adding current 7 to prev 21
Adding current 8 to prev 28
Adding current 9 to prev 36
Adding current 10 to prev 45
55

Recursive leap of faith: the great part about recursive solutions is that one can assume that the function works correctly when called with some simple arguments, and then implement the correct behavior for the current arguments. Similar to calling a function like sqrt, you can assume that the function works for some smaller/simpler arguments and call those to build the current result on top of those. The only requirement is making sure the function will arrive to the base case (like n == 1 in our example) otherwise we would have an infinitely running recursive function and might get a StackOverflow!

In the case of calculating the sum of numbers from 1 up to n, the recursive leap of faith would be to assume that the function correctly calculates the previous sum (the sum for n-1 - prev = sum(n - 1)) and then implement the rest of the function based on that assumption. So, if the current n is 6, we can assume that sum(5) would work correctly and therefore return 6 plus the result of sum(5) at the end.

To check your solution you need to sign in

Sign in to continue