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.*

## 3 comments:

"deferred operations"

This term caught my attention and although I have little insight on compiler operations but this must form an important part of how the compiler handles things.

Hmm.. its not related to compilation, rather it is how the execution flow occurs when executing a recursive function.

I see.

Post a Comment