You now have a couple tools to solve programming, namely iteration and recursion. Both can be used in many situations, but recursion allows us to solve problems in a way that human beings cannot.
For example, let's consider guessing someone's PIN. 8800 is mine. A human being could guess every single possible combination of numbers for a PIN (10,000 possible combinations), but that would take forever. 10,000 guesses is actually a relatively small number of guesses for a computer.
While it's possible to solve this with iteration, it's much easier to do with recursion, and specifically recursive backtracking.
Recursive backtracking still follows all the principles of recursion. Those being :
Recursive backtracking will always have a base case, or it will go forever. In recursive backtracking, we add a concept called "Choose, Explore, Unchoose". When we want to change our state and move towards the base case (the second principles), we will generally have a few choices to make (following the PIN example, 10 choices, one for each number). When we implement recursive backtracking, we do this with Choose, Explore, Unchoose.
Another use for recursive backtracking is finding all the possible different paths to a point. Consider a basic graph; we may want to find all the paths from the origin to the point (5, 5) given that we can only go up or right. So for example, two possible paths might be : Up Up Up Up Up Right Right Right Right Right Up Up Up UP Right Right Right Right Right Up
Base Case : Generally the easiest case, in this situation if the coordinates we are given are (0, 0)
Recursive Case : At every point, we have two choices to make (How many recursive calls do you think we will make each time through the method?) We have to move towards the base case (subtract 1 from X or Y to eventually get to (0, 0))
In [10]:
def pathTo(x, y, path):
#basecase
if x == 0 and y == 0:
print path
#recursive case
#this is an elif because we don't want to recurse forever once we are too far to the right, or too high up
elif x >= 0 and y >= 0:
pathTo(x - 1, y, path + "Right ") #choose right, explore
pathTo(x, y - 1, path + "Up ") #choose up, explore
#pathTo(5, 5, "")
Questions?
What happens if we change the order? How can we make another choice? Why don't we have to Unchoose? How do we stop from going to far?
In [ ]:
def pathTo(x, y, path):
#basecase
if x == 0 and y == 0:
print path
#recursive case
#this is an elif because we don't want to recurse forever once we are too far to the right, or too high up
elif x >= 0 and y >= 0:
pathTo(x - 1, y, path + "E ") #choose right, explore
pathTo(x, y - 1, path + "N ") #choose up, explore
pathTo(x - 1, y - 1, path + "NE ") #choose diagnal, explore
#pathTo(5, 5, "")
Given a PIN, we can use recursive backtracking to "brute force" our way into a solution. This means we are essentially just exhuasting all possible guesses.
We are going to need a second parameter here to start out our soluation
Base Case : The PIN numbers match
Recursive Case : At every point, we have 10 choices to make (one for each number). This looks more like a loop with a recursive call rather than 10 recursive calls.
In [24]:
def hackPassword(correctPassword):
hackPass(correctPassword, "")
def hackPass(correctPassword, guess):
#base case : guess is the correct password
if guess == correctPassword:
print guess
#recursive case : we don't have more than 3 numbers, so make 10 choices
elif len(correctPassword) > len(guess):
for number in range(10):
#choice : add number to guess
#explore : make the recursive call
hackPass(correctPassword, guess + str(number))
hackPassword("8800")
Questions?
Why don't we have to unchoose?
We've all climbed stairs two stairs at a time. Given a number of steps, how many different combinations of stepping once and stepping twice can we climb the given staircase in?
Base Case : The easiest staircase to climb is when we're already at the top, so 0 stairs, or 0 steps left.
Recursive Case : At every point, we have 2 choices to make. 1 step or 2 steps.
What makes this problem more difficult is how we are going to choose to store these steps. In this case, a list is the easiest. Every time we make a choice we will append either 1 or 2 to the list. We finally get to see Unchoose in action here! We have to undo our choice of 1 step before we explore solutions with 2 steps.
In [39]:
import sys
def possibleSteps(steps):
myList = [] #we have to make this list in here so that we have a way to store steps
#gonna draw the staircase for fun
for number in range(steps)[::-1]:
for stepNum in range(number):
sys.stdout.write(' ')
print "__|"
print ""
possibleStepsRecurse(myList, steps)
def possibleStepsRecurse(myList, steps):
#base case : no steps left
if steps == 0:
print myList
#recursive case : don't recurse if we are past the number of steps needed
elif steps > 0:
myList.append(1) # choose
possibleStepsRecurse(myList, steps - 1) # explore
myList.pop() #unchoose
myList.append(2) # choose
possibleStepsRecurse(myList, steps - 2) # explore
myList.pop() # unchoose
possibleSteps(5)
#test comment
In [ ]: