The magic of recursion
I first encountered the concept of recursion in 11th grade, in an object-oriented programming class. At the time, I never really bothered about it that much. But now that I really understand the concept, I realized how magical it is. I was very fascinated to see how elegantly it worked. Sometimes I still wonder how it works.
Last year, I was doing a course on python on edX. And in the course, I again encountered the concept of recursive functions. The professor explained the concept using the example of ‘towers of Hanoi’, which made it all the more interesting. The best part was, the solution for a classic problem like ‘towers of Hanoi’ could be derived using just seven lines of code.
For those of you who don’t know, recursive functions are function that invoke themselves. It works like a loop. The function keeps calling itself until a certain condition is met. All recursive functions can be broadly divided into 2 parts. A condition and a recursive call. A recursive call is what keeps the loop running. And the condition is what stops the loop.
Every time the function is called, the local variables are freshly created. And these variables cannot be accessed by the instance of the function which called it. Ok, I know that’s a little confusing. So, here is an interesting way to understand the working of recursive functions.
Think of a recursive function like the movie Inception. In inception, they go into a dream inside a dream inside a dream. There are multiple levels of dreams where each level is like an image of the real world. And everything that is there in the real world is there in that level of the dream. But the things that get affected in a particular level, stay affected only in that level. They are not affected in the real world or in any other level.
For example, if Cobb (DiCaprio’s character) had lunch in a dream, it does not mean that his stomach will be full in the real world. Likewise, recursive functions also have levels and the local variables within each level in not affected by the change made to that variable in another level.
Within the dreams, they had something called a ‘kick’, which was like a cue for them to exit from that level and go to the previous level. Similarly, in recursive functions, we have if conditions for that. If a particular condition is true, then return to the previous level.
Likewise, a recursive function creates multiple levels of itself and lets you travel through them elegantly. It’s almost magical how recursive functions just work. I don’t believe in real magic. But I feel recursion comes very close.
Here is an example code for solving the ‘Towers of Hanoi’ problem.
As you can see, the only actual operation is the print statement which gets executed when the condition passes. The print statement get executed at every level in a LIFO manner i.e. it gets executed first in the level that was created last and then moves down from there.
But of course, there is a limit to how many times it can call itself. That depends on which language you are using. After the limit is crossed, the stack overflow exception is thrown.
Even today, I still can’t fathom how the concept of recursion works. If any of you know how to explain it, please comment below or reach out to me on google plus. I would really appreciate some insight on it.
I hope you enjoyed this article. If you did, then please consider sharing it to your social networks. Also, I am thinking of writing more articles about fundamental programming concepts that beginners might find hard to understand. If you have any such topics in mind, please do let me know.