Learning objectives
By the end of this section you should be able to
- Describe the concept of recursion.
- Demonstrate how recursion uses simple solutions to build a better solution.
Recursion
Recursion is a problem solving technique that uses the solution to a simpler version of the problem to solve the bigger problem. In turn, the same technique can be applied to the simpler version.
Three Towers and recursion
1.
How is the problem of moving two rings solved using recursion?
-
Move the small ring to the middle tower, move the bigger ring to the target tower, and move the small ring to the target tower.
-
Move two rings from the source tower to the target tower.
-
Cannot be solved with recursion.
2.
How is the problem of moving three rings solved using recursion?
-
Move three rings from the source tower to the target tower.
-
Move two rings to the middle tower, then move the biggest ring to the target tower, and finally, move two rings to the target tower.
-
Cannot be solved with recursion.
3.
How many times is the two-ring solution used with three rings?
-
1
-
2
-
0
Recursion to find a complete solution
The recursion process continues until the problem is small enough, at which point the solution is known or can easily be found. The larger solution can then be built systematically by successively building ever larger solutions until the complete problem is solved.
Solving Three Towers
4.
How many total steps does it take to solve two rings?
-
1
-
2
-
3
5.
How many total steps does it take to solve three rings?
-
3
-
4
-
7
6.
How many total steps does it take to solve four rings?
-
15
-
7
-
3
