What is Recursion?

~ Imagine you have a certain function or a method that performs a particular task, maybe the factorial of a number. Recursion is a programming technique involving a function calling itself. So, every time the function calls itself, the call gets stored in the stack memory. Let's take an example of the factorial function :

We know, 
n! = n * (n - 1) * (n - 2) * (n - 3) * ..... * 1
   = n * (n - 1)!

So, a simple code would be :
int fact(int n){
return n * fact(n - 1);
}

So, suppose you call the function again for n! the idea behind it is to call the function, with a smaller input value. So if we pass the function the value of (n - 1), it'll find (n - 1)! and it can just be multiplied by n to get the factorial of that whole number. Sounds complicated, right? Well, it's not. Let's deep dive into what is the concept behind recursion and how recursion works. But before that, you may ask "If the function is calling itself every time and it's getting stored in the stack memory, it'll start filling up the stack memory right?" Yes, it will. And this condition is known as a stack overflow error. For the above-written code, you can see, the function calls itself an indefinite number of times, (if n = 3, it'll be valid for 3, 2, 1, 0. Then it'll call factorial for -1, - 2, -3, ... so on.)

To avoid this, we use a condition called the Base case.

Base case in Recursion :

In recursion, the base case is a condition, used to terminate the recursive function. It is the condition that stops the recursive calls and allows the function to return a result. Without a base case, a recursive function will continue to call itself indefinitely, resulting in an infinite loop.

So, for the above factorial code, now we can add a base case to it, to terminate the function at some point. Here's the properly written code :

int fact(int n){
if(n == 1)
return 1;
else
return n * fact(n - 1);
}

Now, the program will continue the function call till the value of n reaches 1. For all other values of n, the function makes a recursive call to itself with n-1. This continues until the base case is reached, and the final result is returned.

Recursion and PMI :

Recursion concepts can be proved by a very neat mathematical concept called 'The Principle of Mathematical Induction(PMI)'. Using PMI, we can prove a very simple mathematical formula :

Σn = n * (n + 1) / 2 (Sum of n natural numbers)
So, suppose we want to prove that a function f is true for all natural numbers.
What PMI says is :
1. Prove it is true for a very small value, for 1, or 0. This is known as base case.
2. Assume for the function f, f(k) is true. This is an asssumption, so we do not question this. This is called induction hypothesis.
3. Prove : f(k + 1) is true. This step is called the induction step

Proof :
Σn = n (n + 1) / 2;
Step 1 :
Our first task is to prove it for a small value. So, we prove it for 1 or 0.
Therefore, 
Σ1 = 1 * (1 + 1) / 2
   = 1 * 2/2
   = 1 (Hence proved).

Step 2 : Assume Σk is true.
       Σk = k * ( k + 1) / 2

Step 3 : Prove Σk + 1 is true, i.e, Σk + 1 = (k + 1)(k + 2) / 2.
       Σk = k * (k + 1) / 2  - Eq(1)
       Σk + 1 = (k + 1)(k + 2) / 2 
              = Σk + k + 1   - Eq(2)
       we know, Σk = k(k + 1) / 2, so substituing it in eq(2) :
            Σk + 1 = k(k + 1)/ 2 + k + 1
                   = (k + 1)(k + 2) / 2 (Proved).

Now, several recursion algorithms can be proven to work in the same way. We're going to now look at how we can approach recursion problems, from an angle of PMI :

Problem-solving through Recursion :

While solving a problem through recursion, the first thing we have to understand is if the problem can be divided into similar smaller problems. Then, we gotta follow the similar steps that we performed in the proof of natural numbers, using PMI. Let's take the example of the factorial question. The steps to keep in mind are :

1. Analyse the base case of your problem. In our code, when the value of n becomes 1, it'll return 1 and the loop will break. So, this step is the base case step.

2. Since your function is proven to work for a smaller value, you can assume that recursion will work the same for (n - 1) and return us the value. This is called Leap of faith in Recursion.

3. Finally, we perform our Induction Step, i,e, returning us n * (n - 1). Since our hypothesis will work for (n - 1), we don't have to worry if recursion will figure it out for (n - 1). It will. That's the hypothesis. So, we get the factorial of n.

int fact(int n){
if(n == 1)                        - Base case
return 1;
else
int smallOutput = fact(n -1);     - Induction hypothesis
int ans = n * smallOutput;        - Induction Step.
return ans;
}

Conclusion :

While recursion and PMI are different concepts, they can be used together in several cases. For example, recursive algorithms can be analyzed using PMI to prove their correctness. In this case, the base case corresponds to the smallest input size that can be solved directly, and the induction step corresponds to showing that if the algorithm works correctly for one input size, then it will also work correctly for the next input size.