Recursion and Stack

The concept of recursion, and what’s happening beyond the scene, is from times to times not easy to understand. In this article, we’ll go through a practical example : a recursive function to compute x power y, where x and y are integers.

This is a typical recursive functions :

if (y == 0)
    return (1);

• exit condition : called when y = 0, this will allow the function to stop recursive calls to itself

if (y < 0)
    return (_pow_recursion(x, y + 1) / x);
return (_pow_recursion(x, y - 1) * x);

• recursive statement : increment of decrement y and call back the function _pow_recursion with y + 1 or y -1 : if y is a positive integer, y -1 will decrease to 0 (if y is a negative integer, it will increase to 0)

Since each iteration of the function calls the next, they form a chain of sorts, and exist simultaneously. Each successive function call gets pushed unto the top of the stack, and the function below waits for the return of the function above it.

Here’s what is happening when we execute :

_pow_recursion (4, 3)

The stack is going to be built up :

• calling the recursive function with incrementation or decrementation of the y variable

Our initial Function Call, FC1, is put in the stack and calls FC2.

FC2 is placed on the Top of the stack and calls FC3, etc…

Ultimately FC4 is called : _pow_recursion(4, 0). As y is equal to 0, we’ve reached the exit condition and no more function calls are made.

The return value of FC4 is passed to FC3, FC3 can now return a value which is passed to FC2, etc…

At the end, the Stack is empty and the result is computed :

_pow_recursion(4, 3) = 64

It has to be noted that, in case no exit condition is specified, or if it is poorly specified, the recursive function could call itself indefinitely which will result in a Stack Overflow