Understanding Recursion

Recursion is magic because of how it works and not because of difficulty I guess.
Let me explain it :
See this program for factorial for given number “n” first :

Note* : I used the variable “smallOutput” as we basically are calling the same function (or solving same problem) “factorial” but with a smaller input size of (n-1) , hence answer for smaller input is named as smaller output or smallOutput

Note* : I would have used “smaller problem” term somewhere then it means that same problem but with smaller input i.e. calling same factorial function with smaller input like (n-1).

Did you see the magic ?
You just told your computer that I don’t care how you do it but anyhow get me the factorial(n-1) value, you do just that and then I can solve the problem on my own because I know factorial(n) = n*factorial(n-1) and so all I need to do is just multiply “n” to the value you give me.

This is exactly what you have to do when using recursion.

The critical problem people face while thinking recursion is that they start thinking how would recursion be getting me that factorial(n-1) if I have not asked it to do anything and this is exactly you have to assume.

You have to assume that my computer will certainly give me the correct answer to factorial(n-1) and my only problem now is what I should do now with the factorial(n-1) value I have received.
Well then your logic strikes that all I have to do is multiply “n” to it and return.

Just to show how recursion call stack would be formed is :
Say we call the function for n=3 i.e. finding factorial(3) = 6 see below picture.
https://i.stack.imgur.com/U5nKf.png

Going ahead while using recursion this is the exact temptation of imaging a recursion stack is what you have to avoid to see the magic.

Consider another example of printing numbers from 1 to N :

*Note : Here the smallOutput was not required as we are not using any value returned from recursion but just for the sake of sameness as previous example I used it.

Here you needed to print numbers from 1 to N . Now you said to your computer that dude you print from 1 to N-1 and I’m sure you would do that and once you’re done I’ll just print the last number N.

The best example of recursion’s magic would be MERGESORT.
Just imagine you split the array into 2 half, call mergesort on each half and just think that yeah computer will give me these 2 half as sorted and all I need to do now is to merge these 2 sorted arrays I just received to create the final sorted array. You literally just asked the computer to sort those 2 half without thinking how would the computer know it but all you care about is yourself :P that I can’t sort those 2 halves so you do it and I can merge those 2 sorted halves into a complete sorted array as only that much is what I can do :P .

Adding some technical terms to it now but before that one question :

When can you call recursion for help ?
Say there is a problem for whom you can answer for a very small input you know like factorial(1) = 1 or fibonacci(1) = 1 and fibonacci(2) = 1 BUT solving for a very large input is not easy BUT at the same time you know if someone can give you answer to the same problem but with a smaller input then I can use that result to compute my answer

Example : fibonacci

fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

Now for you fibonacci(n) was difficult to calculate but you said if someone gives you value of fibonacci(n-1) and fibonacci(n-2) you will be able to calculate the answer (by adding those 2 values) . So you put your computer to work that get me those answers and rest I can handle.

This above relation between same problems but one with large input and other with small input is basically called as RECURRENCE RELATION .

Recursion involes 3 steps :

i) Base-Case : this is the problem with small input that you can solve like factorial(1) = 1
ii) Induction hypothesis : the recursive call and assuming it will give correct answer for the smaller input
iii) Induction Step : what you do after the recursive step i.e. induction hypothesis

Note* : Recursive call means calling the same function with a smaller input size like (n-1) like in factorial we call factorial(n-1)

Hypothesis means “supposition” or “assumption” and this is exactly what you do when you make a recursive call i.e. you assume that recursive call will give me the correct answer for the smaller input.

What is my hypothesis here ?
My hypothesis here is that the function factorial(n) will always give the correct answer i.e. correct factorial value of n
Hence it should also give correct answer for factorial(n-1) . This is what we suppose in our recursive step that we would get the correct answer for factorial(n-1).

What is Induction Step ?
It is what is required to be done if that smaller problem is solved.
So in factorial program after we got the factorial(n-1) we needed to multiply it by “n” to get answer for factorial(n) .

Note* : Induction step can come before Induction Hypothesis. Try printing numbers from N to 1 using recursion.

How to think about Base-Case ?
Think of the smallest VALID input possible for this problem like for factorial it is n=1 or n=0 and for fibonacci n=1 and n=2.

We can have multiple base-cases
If your recurrence relation require answer of 2 smaller problem’s of different sizes to compute larger problems answer then you’ll require multiple base cases.

Example fibonacci series 1 1 2 3 5 8 13 …..

fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

The reason both these base cases were required were to avoid infinite recursion. How will that happen ?

Assume that the 2nd condition that if n==2 : return 1 was not there.
Say if n=2 was input, then we would call fibonacci(1) and fibonacci(0) , but fibonacci(0) is not defined and hence it would call fibonacci(-1) and fibonacci(-2) and it can go on till infinity finally exceeding recursion depth and program crashing.

This is the exact purpose a base-case solves that it stops the recursion at a smallest problem whose answer we already know and hence can hardcode it in a way and return its answer.

My suggestion from here onwards would be to try some recursion questions and force yourself to identify all the 3 steps of recursion and writing them in comments and make sure not to think of recursive calls and how are they getting solved.

1 particular fun problem to do would be “Sort an array using recursion” .
Hint :
Base case ? : An array of size 1 is always sorted so if size of array is 1 then return that array
Induction Hypothesis : leaving the element at 0th position, ask the recursion to get you the sorted array from 2nd element to end i.e. arr[1:n]
Induction Step : Since rest of the array is sorted all you need to do is place the element at the 0th position in its correct position . For that you’ll have to iterate through rest of the array which is sorted and compare its value with array element’s value and then moment you get a value greater than 0th element, insert 0th element right before it.

Try Tower of Hanoi problem (google it) and you’ll love it how easy it becomes.
Hint :
Say n = 4 disc:
You don’t know how to place the all the 4 disc from source pillar to destination pillar but if someone can put (n-1) i.e. (4–1) = 3 disc from source pillar to auxillary pillar then you know that you can place the last disc from source to destination pillar and then subsequently place the (n-1) i.e. 3 disc from auxillary pillar to destination pillar and your problem would be solved.