The concept of recursion! and how this function does in the stack?

Recursion logo!

Recursion is a process in which a function calls itself as a subroutine. This allows the function to be repeated several times, since it calls itself during its execution. Functions that incorporate recursion are called recursive functions.

Recursion is often seen as an efficient method of programming since it requires the least amount of code to perform the necessary functions. However, recursion must be incorporated carefully, since it can lead to an infinite loop if no condition is met that will terminate the function.

Example:

Of course, I’m not going to leave you hanging there. Let’s examine how recursion plays out in practice. Take a look at the following algorithm that calculates a number x taken to the power of y:

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);
}

At first glance it looks like a regular short function, yet on a more detailed look, we can see that inside the function, the same function is called again.

This is an example of a recursive function. This function receives two floats, xand yand calculates the result of xto the power of y.

void function()

{

base case()

… … …

function () // recursive call

… … …

}

Example (1)

First, a base case is the condition that allows the algorithm to stop recursing. A base case is typically a problem that is small enough to solve directly. To obey the second law, we must arrange for a change of state that moves the algorithm toward the base case.

A recursive algorithm must have a base case . A recursive algorithm must change its state and move toward the base case . A recursive algorithm must call itself, recursively.

Call stack:

There is usually exactly one call stack associated with a running program (or more accurately, with each task or thread of a process), although additional stacks may be created for signal handling or cooperative multitasking (as with setcontext).

The call stack is what a program uses to keep track of method calls. The call stack is made up of stack frames — one for each method call.

How does the call stack work?

structure of call stack

The stack frame at the top of the stack is for the currently executing routine. The stack frame usually includes at least the following items (in push order).

• the arguments (parameter values) passed to the routine (if any).
• the return address back to the routine’s caller (e.g. in the DrawLine stack frame, an address into DrawSquare's code).
• space for the local variables of the routine (if any).

What recursion does in the stack?:

Now let’s see what happens if you call fact(3) The illustration bellow shows how the stack changes, line by line. The topmost box in the stack tells you what call to fact you’re currently on.

Recursion in call stack

Conclusion:

I hope this article brought you more clarity about recursion in programming and how this function does in the stack.

thanks for reading!