C Programming Recursion

C functions also support recursion – a concept that gives most beginning (and many experienced) programmers severe headaches as they try to wrap their minds around the execution of a recursive function. The idea behind recursion is that a function can call itself in order to complete an iterative process where each successive step is defined in terms of the previous result. The best, and probably easiest example where a recursive function is more efficient than a non-recursive one is the calculation of factorials.

Example

The factorial function on the previous example would be evaluated like this if it were passed a value of 5. This is primarily a conceptual process for the evaluation of this function and is not necessarily the actual way the function is evaluated. The stack shown here is not necessarily the same thing as the main stack implemented by the C compiler.

• In the first iteration, the partial evaluation of 5! = 5 * 4! is pushed onto the stack. It will not be fully evaluated until 4! is calculated.
• In the second iteration, the partial evaluation of 4! = 4 * 3! is pushed onto the stack.
• In the third iteration, the partial evaluation of 3! = 3 * 2! is pushed onto the stack.
• In the fourth iteration, the partial evaluation of 2! = 2 * 1! is pushed onto the stack.
• In the fifth iteration, the full evaluation of 1! = 1 is pushed onto the stack.
• Now, the 1! on level [1] is replaced with the value 1 from level [0] and level [1] is evaluated to 2.
• Next, the 2! on level [2] is replaced with the value 2 from level [1] and level [2] is evaluated to 6.
• Next, the 3! on level [3] is replaced with the value 6 from level [2] and level [3] is evaluated to 24.
• Next, the 4! on level [4] is replaced with the value 24 from level [3] and level [4] is evaluated to 120, which is the final result.