Recursion

HELLO…

In this story I am going to be talking about the very basics of a Recursive function in programming and also go over a example explaining how a recursive function works on the stack !

What is it ?

Recursion in computer science is when a function calls itself to achieve its desired goal. These functions are known as recursive functions…

Recursive Functions:

Recursive functions are compartmentalized into two essential parts. The first being what is know as a Base case

A Base case is a section of code that serves as a point where our recursive algorithm will be terminated.

It is usually a conditional statement outlined in the function below that finds a factorial from a given number.

The second essential part of a recursive function is the call to itself. This call using the example above just refers to the same function with an altered value.

Now that we understand the fundamentals we can visualize a example recursive function…

Example:

In order to understand how a recursive function works on the stack we need to talk about LIFO(last in first out)

Here we have a little depiction of The Stack…

This diagram is depicting how the flow of the Stack works with the (First) slot on the stack being the newest element pushed to it and the (Last) slot on the stack being the one that it will remove if needed.

This is the structure of LIFO with the oldest entry being removed first and the newest being placed at the end aka last in first out…

Now I bet your wondering what any of this has to do with Recursive Functions. Just take a look below !

Here we call our _pow_recursion function with the value (3, 4) which will start our recursive algorithm. The diagram above details the flow of the algorithm and its relation to LIFO.

In this diagram above I illustrate how the original call will call another function and in turn will call another function and so on until our program reaches a base case (arrows on the left of illustrated boxes).

Until our function reaches a base case no function will return.

Once our function hits this base case each return will be processed back to its calling function. The RETURNS IN THE STACK column illustrate the order that the value will be returned in and the arrows on the right of our illustrated boxes show which functions each of these values are being returned too.