Recursion and Stack for Beginners

AhlemKaabi — Sun, 04 Jul 2021 22:20:09 +0000

Hello everyone!

Today’s topic is about the recursion process and what happens at the stack?

Considering the function __pow_recursion(float x, float y) that returns the power of a given number (x^y) using the Recursion.

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

Recursion function is a nested function, which means it calls another function. But what makes it special that it calls itself several times until it reaches the ending conditions (if statements of our case).

The key to understanding any code is to follow the instructions one by one, we will do the same thing with our __pow_recursion() function, taking x = 5 and y = 3.

Now let’s follow the arrows

So the __pow_recursion(5, 3) will return [the return of the function __pow_recursion(5, 2) multiple 5 ].

Then the program will wait until it gets the return of the function __pow_recursion(5,2), that means the program will call to the same function with different arguments, x as 5 and y as 2.

And again, the __pow_recursion(5, 2) will return [the return of the function __pow_recursion(5, 1) multiple 5 ].

Also again, the program will wait until it gets the return of the function __pow_recursion(5,1), now don’t lose your concentration because the program will again call the same function with different arguments, x as 5 and y as 1.

We almost reach the end of our recursion!
The __pow_recursion(5, 1) will return [the return of the function __pow_recursion(5, 0) multiple 5]

float __pow_recursion(float x, float y) /*__pow_recursion(5, 0)*/
{   
    if (y == 0) /*true*/
       return (1); /*our return is 1*/
    if (y < 0)
        return (_pow_recursion(x, y + 1) / x);
    return (_pow_recursion(x, y - 1) * x);
}

So the return of the function(5, 0) is 1.

There is no more calling to our function! The recursion is done! BUT!
Let’s get back to our functions, they are waiting! And give one by one the return needed!
the __pow_recursion(5, 1) will return 1 * 5 = 5
the __pow_recursion(5, 2) will return 5 * 5 = 25
the __pow_recursion(5, 3) will return 25 * 5 = 125

And the execution is DONE!

Now, what happens at the stack? And what is it in the first place?

First, the stack is a data structure with LIFO property that means the last data kept in is the first to go out to use/delete…
Second, a part of the memory took the name of that data structure ‘stack’ because it uses the same property to keep the data!
But what data?
When the program is executed, the variables, function calls, text codes… kept on the stack!
Every instruction in our code/function ran will have a place on the stack, and when it is done/completed, it goes forever. Unlike another type of memory which is the heap, that keeps data forever! And for that, we have to manage that.
The recursion uses the stack for its LIFO property, which makes a function remember its “caller” function, and know to whom it will return its output!

I hope you enjoyed reading and have learned something new!

DEV Community: AhlemKaabi

Recursion and Stack for Beginners