Say my name!
Recursion concepts
What is recursion?
According to Wikipedia recursion occurs when something is defined in terms of itself or of its type.
Precisely for computer science we can say that it is a function that calls itself.
As a programming technique it is one of the so-called “divide and conquer” techniques and is fundamental in the design of many algorithms.
In order to make a recursive call without falling into an infinite repetition it is necessary to determine a base condition, usually associated with a problem that is no longer possible to divide or unglobe.
For example, whenever we call a function in C, the local variables and function parameters are stored in stack memory, the data are stored and removed in a LIFO (last in, first out) pattern.
This is how it works. When a function requests space for local variables, the allocated space is added to the top of the stack. When the end of the function is reached, the space allocated for local variables appears at the top of the stack.
Variables that are stored in stack-based memory cannot be dynamically allocated during program execution. However this type of memory allocation performs heap-based storage.
Stack overflow can occur due to the limited space available for stack-based memory, but it is just as necessary to define the base condition. One of the most common causes of stack overflow is infinite recursion, a behavior we must be aware of when programming recursive functions.
Let’s look at the following example of an algorithm written in the C programming language:
Stacking
The function calls itself, and if the base condition is not met, it recursively calls itself again. A stack of new local variables and parameters is added to the existing memory stack with each function call.
When the base case is reached the magic happens, and the base case response is used to answer the previous calls. It returns answering each function call by removing from the stack the data associated with each instance.
Finally the last stack is removed and the final response is obtained.
