Recursion in Python

In computer science, recursion is a method of finding solutions to problems using smaller solutions of the same problem. Recursive Algorithms have applications in list sorting, binary tree traversal, path finding and much more. In this post, we will discuss a classic recursive procedure used to find the factorial of a natural number.

Let’s get started!

Since we will be writing an algorithm to find factorials, it is worth reviewing the definition of a factorial. The factorial of a natural number, n, is the product of all natural numbers less than or equal to n:

For example, if n=6:

Let’s think about this recursively. If we have a recursive function f, we’d want to use f to calculate 6! in the following way:

6! = f(6)

f(6) = 6*f(5)

f(5) = 5f(4), so f(6) = 65*f(4)

f(4) = 4f(3), so f(6) = 654f(3)

f(3) = 3f(2), so f(6) = 6543*f(2)

f(2) = 2f(1), so f(6) = 65432f(1)

f(1) = 1, so f(6) = 65432*1.

To implement this in Python, we need to define a function, we’ll call ‘recursive_factorial’, that takes input n, and returns n*recursive_factorial(n-1). Moreover, we’d like the function to keep returning itself until the input is equal to one. At that point we return 1 and the recursion terminates. To implement this we do the following:

def recursive_factorial(n):
    if n == 1:
        return 1
    else:
        return n*recursive_factorial(n-1)

Additionally, we should handle the case where n =0, given 0! =1. Let’s change the if-statement appropriately:

def recursive_factorial(n):
    if n <= 1:
        return 1
    else:
        return n*recursive_factorial(n-1)

Another thing worth noting is that our function does not handle negative numbers. This method only works for the natural numbers and zero.

Let’s consider what this function is doing for 4!:

We have to calculate recursive_factorial(4).

The function asks, is n = 1? No, n=4, so let's return 4*recursive_factorial(4 - 1), which is 4*recursive_factorial(3).

Now we have to calculate recursive_factorial(3). 

Is n = 1? No, n=3, so let's return 4*3*recursive_factorial(3 - 1), which is 4*3*recursive_factorial(2).

Now we have to calculate recursive_factorial(2).

Is n = 1? No, n=2, so let's return 4*3*2recursive_factorial(2 - 1), which is 4*3*2recursive_factorial(1).

Now we have to calculate recursive_factorial(1).

Is n = 1? yes, n=1, so let's return 4*3*2*1.

The cases where n > 1 are called recursive cases and when n <= 1 we have the base case.

Based off of this logic, recursive_factorial(4) = 432*1 = 24. Let’s validate this:

def recursive_factorial(n):
    if n <= 1:
        return 1
    else:
        return n*recursive_factorial(n-1)
print("4! =", recursive_factorial(4))

Let’s try the earlier example, 6!:

print("6! =", recursive_factorial(6))

I’ll stop here but feel free to play around with the code. If you’re interested in learning more about recursion python-course.edu is a good resource.

To summarize, in this post we discussed how to write a recursive algorithm to find the factorial of a natural number. Other classic applications of recursion algorithms include The Towers of Hanoi Problem and The _N_th Stair Problem. I hope you found this post useful/interesting. The code from this post is available on GitHub. Thank you for reading!