Siddharta Govindaraj
/home/siddhi

/home/siddhi

Recursion Part 1: Introduction to Recursion

Photo by Giordano Rossoni on Unsplash

Recursion Part 1: Introduction to Recursion

Siddharta Govindaraj's photo
Siddharta Govindaraj
·Apr 18, 2022·

2 min read

This is a series of articles on recursion that I had on my old blog. Since Hashnode doesn't seem to have a way to import posts from Blogger (where my old blog was hosted), I am re-posting here. I have also taken this opportunity to rewrite the code snippets from C -- which I used at that time -- into Python, which is my preferred teaching language nowdays.


In this, the first part, we talk about some theory behind recursion. This theory will form the foundation and help in understanding the remaining parts of the series. Most of this theory will already be known and it is just a quick overview to refresh your memory.

Let us start with the most common example of recursion, calculating the factorial of a number. Here is the code:

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

How does this work? Say we want to calculate factorial(4). Since 4 is not equal to 0, the expression evaluates to 4 * factorial(3). factorial(3) in turn is expanded to 3 * factorial(2). At each point, the previous state of execution is pushed on to the stack. Continuing this way, the expression finally evaluates to: 4 * 3 * 2 * 1 * factorial(0)

factorial(0) is the base case and matches if n == 0 which returns 1.

At this point, the stack of operations gets popped and the value changes as follows:

4 * 3 * 2 * 1 * 1
4 * 3 * 2 * 1
4 * 3 * 2
4 * 6
24

The final answer is 24, which is indeed the factorial of 4. Let us summarize the state of execution at every step:

factorial(4)
4 * factorial(3)
4 * 3 * factorial(2)
4 * 3 * 2 * factorial(1)
4 * 3 * 2 * 1 * factorial(0)
4 * 3 * 2 * 1 * 1
4 * 3 * 2 * 1
4 * 3 * 2
4 * 6
24

Note an important point: No multiplications are performed until the stack starts to get popped. Thus, the execution of this function consists of a series of "deferred operations" which are stored in the stack state during the push operation, and which are executed after the pop operation.

Understanding the above point is the key to understanding many concepts in recursion. We will be using it in the other articles in this series.

 
Share this