Skip to main content

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.

Comments

Popular posts from this blog

HOW TO USE THE DELAY FUNCTION IN C++

Hello programmers!!

Have you ever wondered how people use that effect, in C++ console applications, in which they make characters appear after a certain time. Like they say "loading..." and the cots appear one by one at a particular time interval. This effect looks very cool and makes the applications look very professional.Also see : Basic Algorithms 101 : Checking the validity of an email address (simple beginner approach)

Also see :Basic Algorithms 101 : Checking the validity of an email address (simple beginner approach) 
This 'effect' is called delay. Delay is a more professional term used for some thing that happens a little later than it is expected to happen. This is used in c++ intentionally to either create an 'effect' or to easy the procedures of the application for the user.  Like there are manyuses of the delay function.

Usually in C++ the output appears in the console as soon as it is executed. This might make it look like the application is mad…

HOW TO COPY ANY TEXT TO TURBO C++

Hello!!

Are you one of those people who is in the middle of a C++ program and you know what to do, but you don't know the syntax? So you google and find out the syntax. But in turbo c++ you cannot use ctrl+v. That might be a little pissing off. So the easiest solution would be to get rid of Turbo C++ and get a modern day compiler. But anyway, here is a post on how one can copy text from an external source into the turbo C++ environment.



Also see:Basic algorithms 101 : Checking for the validity of an email address (simple beginner approch) 
C++ is a very powerful language, but the Turbo C++ compiler is bloody ancient and very conservative. The Unix environment it has can be a pain in the neck sometimes. With the modern day compilers like C++ builder, eclipse, and stuff, programming in C++ has become so much easier. Unix environment is not really necessary to build an application. And these new compilers also have a lot of predefined functions for graphics, user interface etc.

Somet…

How to geek: Learn to code like a pro

Warning! Philosophical text ahead. Skip to the next section to avoid it.
A lot of people come up with a lot of brilliant ideas. But not all of them are able to execute their ideas due to lack of programming knowledge. Lack of programming knowledge is something that can only be solved by sitting your ass down and doing a course patiently without giving any excuses. It is important to assess yourself thoroughly. If you don’t know something, you need to accept it. You can’t call yourself a web developer after editing a few HTML templates. If you want to be a web developer, stop editing templates and start building one from scratch. Speed is not more important than fundamentals. If you go after speed, you will end up becoming like season one flash. Another thing I’ve noticed in people is, they are not able to stay motivated for more than a day. They start a course online, binge watch a few videos and then forget about it the next day. An online course is not the same as a TV show. You ca…