The Science of Recursive Functions for Dummies
First a brief intro of recursive functions…
A function is called a recursive function if it calls itself again and again .
Recursion can be direct as well as indirect.
Direct recursion is when a function calls itself. Whereas indirect recursion is when a function calls another function and the called function in turn calls the calling function.
That is if function 1 calls function 2 and then function 2 calls function 1 resulting in a cycle.
Now let's understand what exactly recursion is and what is it used for…
Let’s take an example . Suppose we have a word(problem) which is unknown to us . We need to find it’s meaning, so we shall look it up in dictionary(function).
But when we look at the meaning we find that the meaning in turn contains yet another word which we don't understand. So we have a solution but this solution contains a part that is still problematic. In order to fully understand the meaning of the original word we need to first understand the meaning of the problematic word in the meaning of the original word.
To do so we again search the dictionary for the meaning of the new problematic word. That is we follow the same path as we did in the first step.
We shall repeat this process until we find a solution that doesn't contain any problematic word.
This is what recursion is for . We have a problem at hand and in order to find it's solution we follow a certain path . We obtain a solution but this solution still has some problematic part. In order to find the complete solution we need to first solve the problematic part. To do so we follow the same path which we followed in the first step. That is call the same function again. We do this until we find a solution that completely makes sense to us . This is the terminating step.
As an example let’s see a program to find a factorial of a number using Recursive functions.
#include<iostream>
using namespace std;
int factorial(int n);
int main() {
int n;
cout << "Enter a positive integer: "; cin >> n;
cout << "Factorial of " << n << " = " << factorial(n);
return 0;
}
int factorial(int n) {
if(n > 1)
return n * factorial(n - 1);
else return 1;
}
If here n is given a value 5. The factorial function will be invoked for 5, the solution that this function would come up with in the first pass would be 5*4! Here the problematic part in this solution is 4! So the factorial function would call itself again but this time for 4 . This process will repeat until we have no term as n! The last time the factorial function would be called is for 1! which will return 1 as answer and then by tracing back we will get the solution for 5!
Note : It might happen that we never reach a terminating case. This is known as infinite recursion.
In the dictionary examples above this can explained as…
When we look up for the meaning of the original word we find a problematic word and when we search for the meaning of the problematic word we in turn find the original word in its definition . That is we will keep going in a cycle indefinitely as there's no terminating case.
Here you can find more on recursion.
About Me
I’m a Senior Product Engineer from India, working in web and mobile development. I enjoy turning complex problems into simple, beautiful, and intuitive software. I blog to share my software knowledge with others.
My job is to build your idea so that it is functional and user-friendly but at the same time attractive. Moreover, I add a personal touch to your product and make sure that is eye-catching and easy to use. I aim to help you validate and scale your startup most creatively.
Quick Links
✉️ Subscribe to CodeBurst’s once-weekly Email Blast, 🐦 Follow CodeBurst on Twitter, view 🗺️ The 2018 Web Developer Roadmap, and 🕸️ Learn Full Stack Web Development.
