Recursion, Recursion, Recursion
What Is Recursion?
Have you ever went to ask your mom can you have something (it could be anything), and then she tells you to go ask your dad? And then when you finally get to your dad he tells you to go ask your mother? This is a forever non-ending loop that goes on until one your parents just gives you the yes or no. That is recursion because you are constantly repeating yourself going back and forth with your parents until you reach an answer that fulfills your question.
You can imagine the question as a function with its parameter being (a) for the answer. You will continuously call this function in hopes of receiving the answer “yes”. I will provide a code snippet below as an example.
In this snippet if you are given an answer of yes or no this code will return your answer given to you by your parents. However if you receive anything else, in this case “go ask mom/dad” you will repeat this function again. This is how you use recursion in the most simplest way.
Recursion is a very fundamental skill that can be extremely useful to those who decide to use it. A function is only considered recursive when the function calls itself, this is a very important thing to always know when trying to implement.
How would I use this in a programming problem?
To show you how to use this in a problem we will be using the “Fibonacci Number” question that you can find on the website leetcode. The Fibonacci sequence is defined as each number is the sum of two numbers that come before it, the equation is F(N)=F(N-1)+F(N-2). So in the case of F(2) We would get 1 + 0, so F(2) is 1. In this problem we will have to find the value of F(N) given any N number starting from 0 and 1.
To begin we would have to present a base case so that we do not end up with an infinite loop so to do that we would have to return N if N is less than or equal to 1 because this is where we are starting from. We can do this because F(0) is 0 and F(1) is 1. If our N is not one of those two values then we need to continue to call our function recursively so that we can continuously get our sum of N until we reach our base cases.
Below is a tree that shows what our function would be doing under the hood if we were to be solving F(5).
So as I mentioned earlier in this tree you can see how the sum of N is constantly calculated until we reach our base case. Doing it this way will result in a slower time complexity.
We are going to have a time complexity of O(2^n) because if you remember the tree every time we are converting a F(N) we call another two so it would be F(N-1) and F(N-2).
Above is an image of the call stack that I drew showing the order of operations when using the recursive solution I showed you all. In this image we are trying to again find the F(5) so to do this we are finding F(4) and then F(3) and so on. All of the N numbers go into the call stack by order to just hang inside of the memory waiting for the response of the F(N)s above them. So once you hit your base case you will go back up the call stack a you are now finished with your computations.
Wrap Up
I would like to take this time to now refer back to the beginning image I showed you above after hopefully bringing you to some level of understanding of recursion.
The caption I put under this image the first time was that you must first understand recursion to understand recursion, and now that you do understand recursion you can look at this tree and understand that it is indeed recursion. It is a single tree that has branches that are literally Y shapes being repeated over and over again so that the structure then grows into a full bloomed tree with what seems to be leaves. With this in mind you can just think about what else is it possible to create with recursion, and when you figure that out try it and see what you can do there is a plethora of memes out there that use recursion that are very funny as-well. Thank you for reading and I really hope that you learned something today and I hope you pass it forward because that’s what it’s all about.
