Recursion : Hate it or Love it???

People say, “Recursion, It is the toughest and most difficult part for a new coder in competitive programming.. People even cry when they do it”. But is it the case?? No, I don’t think so… If You see recursion from my eyes, I don’t think recursion is that tough. It is just like ghosts.. People are afraid of ghosts but do they even exist???

Recursion by defination is calling a function from within the function.

I was taught recursion by Mr. Sumeet Malik at Coding Blocks. I thank him that he taught me in such a way that coding in recursion feels so easy.

I see recursion just like Principle of Mathematical Induction (PMI), we did it in 11th standard. PMI says that we proove a theorem for n = 1, then we asume that the theorem works for n = k and in the end we proove the theorem for n = k + 1, so if we are able to proove it, then we are assured that the theorem is true for all natural numbers.

Recursion is very similar to it:

You just need to look at the problem in 3 steps:

1. Assume that the function works for all the cases which are smaller than current case.
2. Next, We do the job that needs to be done for the present case.
3. And Last We do the job for the base case.

Let Us Understand it using a simple problem, suppose we need to print numbers upto N in decreasing order.

Step 1 : Make Assumption that the function works for N-1.
public static void printInDecreasing(int N){
// Assumption
printInDecreasing(N - 1);
}

We assume that by just writing “printInDecreasing(N-1)” the code will print decreasing numbers upto N-1,
That is, if N = 10, then by writing this line we get:

OUTPUT(Assumption):
9
8
7
6
5
4
3
2
1

Step 2 : We do the job that is required for the present case.
public static void printInDecreasing(int N){
// My Job 
System.out.println(N);
//Assumption
printInDecreasing(N - 1);
}

So by writing System.out.println(N); we do the job of printing N, and as we had to print in decreasing order so, if N = 10, then 10 needs to be printed before 9, 8, .. so we write it above the assumption line.

OUTPUT(Assumption):
10
9
8
7
6
5
4
3
2
1

Step 3: We write the base case.
public static void printInDecreasing(int N){
//Base Case
if(N == 1){
System.out.println(1);
return;
}
// My Job 
System.out.println(N);
//Assumption
printInDecreasing(N - 1);
}

So we write the base case which is hit when the code runs, we decreased the value of N by N-1 this way the value of N reaches 1 and the work that needs to be done at that point is written in the base case. This way the recursive code for printing decreasing numbers is written…

OUTPUT:
10
9
8
7
6
5
4
3
2
1

This way any problem of recursion can be solved with easy. You just need to see it in these three basic steps.

I would suggest now to write the code for printing numbers in increasing numbers recursively for better understanding.

Hint : You Just Need to change one line in the previous code.