## Wednesday, April 12, 2006

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

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 * 14 * 3 * 2 * 14 * 3 * 24 * 624`

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 * 14 * 3 * 2 * 14 * 3 * 24 * 624`

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.