Home arrow Practices arrow Solving Problems with Recursion

Solving Problems with Recursion

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!

TABLE OF CONTENTS:
  1. Solving Problems with Recursion
  2. The Plot Thickens
  3. First Programming Example
  4. The Flood Fill Algorithm
  5. How it Works
  6. Connect 4 AI program
  7. The Minimax Method
  8. Placing Pieces
  9. Trying it Out
  10. Two More Tips
By: Mohamed Saad
Rating: starstarstarstarstar / 54
November 17, 2004

print this article
SEARCH DEV SHED

TOOLS YOU CAN USE

advertisement

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."

Solving Problems with Recursion

Fig 1. You never knew knowing your house number could get you into so much trouble, did you?



 
 
>>> More Practices Articles          >>> More By Mohamed Saad
 

blog comments powered by Disqus
escort Bursa Bursa escort Antalya eskort
   

PRACTICES ARTICLES

- Calculating Development Project Costs
- More Techniques for Finding Things
- Finding Things
- Finishing the System`s Outlines
- The System in So Many Words
- Basic Data Types and Calculations
- What`s the Address? Pointers
- Design with ArgoUML
- Pragmatic Guidelines: Diagrams That Work
- Five-Step UML: OOAD for Short Attention Span...
- Five-Step UML: OOAD for Short Attention Span...
- Introducing UML: Object-Oriented Analysis an...
- Class and Object Diagrams
- Class Relationships
- Classes

Developer Shed Affiliates

 


Dev Shed Tutorial Topics: