Recursion Visualized

Because pictures are worth a thousand words

Recursion is the process of a function calling itself. It creates a loop between the start of the function and any line which contains a recursive call. To avoid an infinite loop, the function needs a base case which terminates the function. When the base case is reached, the function returns to the prior recursive call (if any) and resumes execution.

The general code execution flow can be visualized as follows:

Phase 1: Input loop

In this phase, input is checked for meeting the base case requirement(s), and if it fails, the function calls itself with different parameters. This continues until…

Phase 2: Base case

In this phase, the input matches the base case, and the function returns without further recursion.

Phase 3: Return loop

Finally, with the base case reached, and a value returned, prior function calls can resolve any statements dependent upon the return value of their recursive call. As those calls return, the function “unwinds” so to speak, as it each instance of the function finishes execution from the line where the recursive call was made. This pattern could continue if there are multiple lines of recursive calls, but this illustrates the basic pattern.

The Call Stack

In order to keep track of all the function calls, functions are pushed onto the call stack. The call stack (or stack for short, though not all stacks are call stacks), is a region of memory of a fixed size, usually around 1MB. A stack of that size can handle a recursion depth of about 10,000 depending on the size of the stack frame. If a function recurses too many times it can potentially run out of stack memory, causing a stack overflow. Every time a function is called, it is pushed onto the stack. Whenever a function returns, it is popped off of the stack. Only the function at the top of the stack will run at a time.

Example

Here is a function which uses a recursive algorithm to determine to calculate x to the y power.

float _pow_recursion(float x, float y)
{
    if (y == 0)
        return (1);
    if (y < 0)
        return (_pow_recursion(x, y + 1) / x);

    return (_pow_recursion(x, y - 1) * x);
}

This function will recurse if y != 0 . The base case is when y == 0 , in which case the function returns 1.

Here is a graph of the whole process:

graph of recursion and the call stack

Recursion is often confusing to wrap ones head around, so I hope this post elucidated the process.