The Plot Thickens - Practices

To confuse things even more, let's say you visited the house next to you, but you still found no number. You knocked on the door, and asked about the house number. Guess what they said to you? "We don't know, but look at the house next to us, add 1, and you will know our house number."

Déjà vu anyone? This game could take a while. You should repeat this again and again, till you find a house with a number you know. You add 1, and know the number of the one next to it, and so on, until you reach your house.

Notice that in every step, your problem was always reduced to exactly the same kind of problem (knowing a house number). This is the heart of recursion. We have just made our first recursive solution to a problem.

Before we go any further, I want to make two very important notes. These notes are going to be extremely useful when we start dealing with recursion in programming.

Note 1: In every step of solving a recursive problem, the problem always reduces to a problem of exactly the same nature.

This one is obvious, but now look at number 2.

Note 2: At a certain point, you should just solve the problem you have immediately rather than reducing it any further.

This note is extremely important. Let's return back to our house numbers problem. If you just keep asking and you are always asked to see the next house, you will spend your entire lifetime looking at buildings! At a certain point, you have to find a house with a number that you know. At this point, the recursion stops, and you start to solve all the problems you left open.

Let me stress this again: you can't keep reducing your problem into a similar problem forever, or else you are never going to stop. At a certain point, you have to just stop and solve the problem at hand. This point is sometimes called the stopping condition.

Now, I can already hear you screaming, "What does this have to do with programming?!" Well, a lot, actually. When you are writing a program, you are solving a problem (or a set of problems). If you write your solution to the problem in a recursive way, what will it look like? Basically the function you write to solve the problem is going to eventually call itself. What for? This comes from our definition of recursion. We reduce a problem to a problem of exactly the same nature. This is why the function calls itself to solve the new instance of the problem...

Sounds complicated? Don't worry. Let's look at our first programming example, a really simple one.