Stepping stones to understand RECURSION
A Brilliant method to solve problems by breaking them down into smaller, repetitive problems
Have you ever tried typing the word “recursion” in the google search?
Here is what the search results show.
I went through the spellings several times to figure out the mistake before realizing Google once again was pulling an inside joke.
Well, the definition of recursion states,
“the repeated application of a recursive procedure or definition is known as recursion”.
When I first read this definition, it sounded like Greek to me!
Recursion can look like a very complicated topic to the unfamiliar mind. But not to worry too much! By the end of this article, you will understand it just enough.
What is RECURSION?
Simply put, recursion is the process of defining a problem and its solution in terms of itself or a smaller version of itself.
This definition’s visual form is shown in the above figure known as the “Droste effect.” The woman on the cover is holding an object containing a smaller image of her holding a similar object, which in turn contains a smaller image of herself holding an identical object, and so forth.
Let us take some common examples to understand this concept more clearly.
A list can be considered as a list of lists!
2. Factorial of a number n can be written in terms of the factorial of a smaller number.
3. Recursion is also very commonly found in nature. Take a close look at a part of the broccoli sitting in your kitchen. Can you see the repetition of the same pattern over and over again?
From the above examples, I hope you got a general idea of what recursion truly is. It is merely dividing the larger problem at hand into a smaller version of itself so that we can solve it more easily.
How to solve a problem using recursion?
To solve a problem using recursion, you simply have to
“THINK RECURSIVELY”!
Try to break the problem into a smaller problem with an identical form.
But now comes the questions,
Where should I stop breaking the problem into smaller pieces?
How to get to a conclusive answer to a problem using recursion?
There are three rules a proper recursive algorithm must follow.
A recursive algorithm MUST
- Have a termination (base) condition.
- Have a progressive approach that will lead CLOSER to the base criteria each time a recursive call is made.
- Call itself directly or indirectly recursively.
Termination(Base) condition: A termination criteria must be inserted to ensure that the recursive process comes to an end at some point. Without this condition, the process will go in an infinite loop, resulting in a stack overflow.
Progressive approach: Some of the data used by the algorithm must be modified so that the algorithm is one step closer to the base case after each recursive function call.
Call itself: This is the very definition of recursion. To solve the problem using the same function, it must be called repeatedly until the base criterion is satisfied.
How does a recursive algorithm work?
A recursive algorithm containing the above rules go through two phases before reaching the solution.
- Winding phase: Invoking itself to solve a smaller version of the problem
- Unwinding phase: Building up the answers of the smaller instances
Let’s look at these phases using an example.
Consider the recursive C program below written to obtain the factorial of a positive integer.
Explanation
Factorial of a number n can be obtained using the factorial of n-1
n! = n * (n-1)
Therefore, the factorial function must be called recursively, with n replaced by n-1 in each function call. Since 0! is 1, we can consider this as the base condition.
Note that the program will result in a segmentation fault without the base condition due to stack overflow.
Let us try to trace this recursive code to calculate factorial 3.
The above diagram clearly shows the winding and unwinding processes. During the winding process, the factorial function is called recursively until the base condition is satisfied when fact(0) is called. After that, the unwinding process takes place using the base condition’s return value until the result (3) is returned.
Memory allocation in a recursive program
It is crucial to understand how memory is allocated during a recursive process and understand the recursion concepts.
A function call creates an activation record containing local variables and the return address. A temporary memory allocation known as the stack stores these activation records until the function returns a value.
A recursive function creates many activation records because it’s called repeatedly until the base condition is satisfied. During the winding process, the records are created. During the unwinding process, these records are erased after each function returns a value to the caller.
Recap
I hope that you got a general idea about recursion. The key things to remember when building a recursive algorithm are,
- Do not forget to add the base condition(s), allowing the function to conclude (without running forever).
- Recursion helps to come up with more straightforward solutions to more significant problems. However, keep in mind, recursive programs tend to take up too much space in the stack. Therefore, do not go for the recursive solution if the iterative solution is much easier to obtain.
Finally, to truly understand recursion, you might want to go through this article !
