Recursion and Recursive Functions in Python

Today we’ll be talking about recursive functions. Recursive functions are functions that call themselves.

A typical example shown when recursion is discussed is the function that returns the factorial of a number.

Factorials Recap

Well, let’s briefly talk about factorials in case you don’t remember well what they are.

To calculate the factorial of a number, you have to multiply the number by all the integers less than the number, down to 1. So,

5! = 5 * 4 * 3 * 2 * 1 = 120

or more generally:

n! = n * (n – 1) * (n – 2) * (n – 3) * … * 1

Now, back to our first example. If

5! = 5 * 4 * 3 * 2 * 1

and

4! = 4 * 3 * 2 * 1

then

5! = 5 * 4!

and more generally:

n! = n * (n – 1)!

So, as you can see, in order to calculate the factorial of 5, we multiply 5 by the factorial of 4. But to calculate the factorial of 4, we multiply 4 by the factorial of 3, and so on.

So, if we define a function that calculates the factorial of the number n, we have to use the same function in its body to calculate the factorial of the number one less than n.

Learn how to make beautiful GUI apps

in Python using the Kivy framework.

Comprehensive, for Kivy beginners, easy to follow.

Get the book here (PDF) or on Amazon:

ebook / paperback (black and white) / paperback (full color)

Recursive Case and Base Case

Now we are almost ready to write our function code. There is one thing we must mention before we do. A recursive function calls itself repeatedly, but how long should it go on like that? When is it supposed to stop? This must be specified in the function definition.

When we define recursive functions we have to specify two cases in their body: the recursive case and the base case.

The recursive case is the condition for which the function should call itself.

The base case is the condition for which the function should stop calling itself.

Let’s illustrate it on our example:

The function should call itself as long as the integer is greater than 1. When it’s equal to 1, it should stop calling itself.

So, our base case is n = 1.

Our recursive case is n!= 1.

So, here’s our code, the function definition and call:

def factorial(n):
    # base case: n = 1
    if n == 1:
        return 1
    # recursive case
    else:
        return n * factorial(n - 1)


print(factorial(5))

The output is:

120

What’s going on when we call a recursive function like this? Well, each recursive call adds a stack frame with its execution context to the call stack. When the base case is reached, the stack begins to unwind as each call returns its result.

If we wanted to write this function without recursion, we could do it like so:

def factorial(n):
    result = n
    while n > 1:
        result *= (n - 1)
        n -= 1
    return result

print(factorial(5))

The result will be the same as when we used the recursive version.

By the way, there is a factorial function in the math module, so you don’t have to define it yourself.

Your Panda3D Magazine

Make Awesome Games and Other 3D Apps

with Panda3D and Blender using Python.

Cool stuff, easy to follow articles.

Get the magazine here (PDF).

Recursion with Nested Structures

Another typical situation when recursion comes in handy is handling arbitrarily nested structures. For example the folder system: we can have folders inside other folders, and there may be yet other folders inside these folders, and so on. The structure of folders may be of arbitrary complexity.

Let’s represent our folder system as a list. The outer list is the root folder, the nested lists are subfolders:

folders = ['f1', ['f2_1', 'f2_2'], ['f3_1', ['f3_1_1', 'f3_1_2']]]

Now we want to create a function that takes a list of folders and does two things:

– changes the name of each folder replacing ‘f’ with ‘folder’,

– prints the structure of the folders in a neat tree form.

Now, if an element of the list is a nested list, the function should be called recursively for that list.

Here’s how we can do it:

folders = ['f1', ['f2_1', 'f2_2'], ['f3_1', ['f3_1_1', 'f3_1_2']]]

def print_folders(folders, level):     
    for folder in folders:         
        if not isinstance(folder, list): 
            folder = folder.replace('f', 'folder ')            
            print(f"|{level * '----'} {folder}")             
        else:               
            print_folders(folder, level + 1)

print_folders(folders, 0)

The output is:

| folder 1
|---- folder 2_1
|---- folder 2_2
|---- folder 3_1
|-------- folder 3_1_1
|-------- folder 3_1_2

Python Jumpstart Course

Learn the basics of Python, including OOP.

with lots of exercises, easy to follow

The course is available on Udemy.

Direct and Indirect Recursion

In the examples above we had direct recursion, so the function called itself. But there can also be indirect recursion, where function A calls function B that calls function A again. Here’s an example:

def A(x):
    print(x)
    if x == 1:         
        return x
    else:      
        return B(x)

def B(x):    
    return A(x - 1)

A(5)

The output is:

5
4
3
2
1

Recursion has its advantages and disadvantages. On one hand it breaks a complex task down into simpler tasks and makes the code clean. On the other hand it’s expensive, which means it takes up a lot of memory and time, so we should use recursion reasonably.

Blender Jumpstart Course

Learn the basics of 3D modeling in Blender.

step-by-step, easy to follow, visually rich

The course is available on Udemy and on Skillshare.

Here’s the video version of this article: