Recursion Part 1: Introduction to Recursion

The following is a part of a series of articles I had written on recursion for a newsletter.

---

This is the first part of a mini-series of full length articles dealing with recursion. 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.

All Parts:

Recursion Part 1: Introduction to recursion
Recursion Part 2: Tail recursion, Accumulators and Iteration
Recursion Part 3: Exercises in tail recursion
Recursion Part 4: Tree Recursion and Dynamic Programming
Recursion Part 5: Structural and Generative Recursion
Recursion Part 6: References and Further Information

---

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

int factorial(int n)
{
    if (0 == n) {
        return 1;
    } else {
        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 evaluates to:

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

factorial(0) is 1, so we get:

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.

---

Any questions? Comments? Please leave a comment using the comment form below.

This post is a part of the selected archive.