Solving Problems with Recursion (Page 1 of 10 )
Recursion is a way to solve a problem by...reducing it to the same problem. What? It may be counterintuitive, but many turn-based games (including chess) use exactly this technique to make a computer player "think." Mohamed Saad explains the concept, along with when (and when not) to use recursion in your programming. Check out the Connect4 example!
Recursion: Solving problems the recursive way
In this article, I will introduce the concept of recursion, one of the most amazing programming constructs, as you will see. Recursion is quite counter-intuitive, and you will certainly find it weird at first, but once grasped, it becomes a seriously powerful weapon in your programming arsenal. Let's start with the definition.
What is Recursion?
Recursion is a totally different method of solving problems. Conventional problem solving methods consists of decomposing the solution into steps, and executing each step in turn. Well…enter recursion. The recursive way of solving a problem is to reduce the problem into another problem that is exactly of the same type, and solving the new one instead. And how do you solve the new one? Guess what? You just reduce it into another problem of exactly the same type, and so on, and so on, and so on…
Ok, before it gets too weird, let's see an example of a real-life problem, and how we can use recursion to solve it.
Real Life Example
Let's assume you have moved to a new apartment. You are exploring the neighborhood, and you suddenly discover that you don't know your house number. You looked at the building, didn't find a number there. You knocked on a random apartment, and asked, "what is the number of this building," and the guy who opened the door smiled and said, "I don't know the number of this building, but if you look at the number of the building next to us and add 1, you will know our building number."
Now, let's pause for a moment. The problem you are trying to solve is "knowing the number of your house." Let's look at the proposed solution to this problem. What was the suggestion? You were asked to look at the number of the building next to you and add 1. Your problem was thus reduced into a problem of exactly the same nature! At first your problem was "to find the number of a house," and your problem now became "finding the number of a house."
Fig 1. You never knew knowing your house number could get you into so much trouble, did you?
Next: The Plot Thickens >>
More Practices Articles
More By Mohamed Saad
/ 32 
