Picture is Worth 1,500 Words

Concept of Recursion in the STACK

  • A simple base case (or cases) — a terminating scenario that does not use recursion to produce an answer
  • A recursive step — a set of rules that reduces all successive cases toward the base case.

for example:

This is a typical recursive functions a recursive function to compute x power y, where x and y are integers:

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);
}
  • base case:

when y = 0, this will allow the function to stop recursive calls to itself

if (y == 0)
return (1);
  • 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)
if (y < 0)
return (_pow_recursion(x, y + 1) / x);

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

what is happening when we execute : _pow_recursion (4, 3).

Building of the STACK:

STACK BUILDING

the recursive function call with incrementation or decrementation of the y variable

Our initial Function Call, F1, is put in the stack and calls F2. F2 is placed on the Top of the stack and calls F3, …Ultimately F4 is called : _pow_recursion(4, 0). As y is equal to 0, we’ve reached to exit condition (base case).

Resolution of the STACK:

The return value of F4 is passed to F3, and now F3 can return a value which is passed to F2, … at the and, _pow_recursion(4, 3) = 64

……the stack is empty.