There are some problems for which we haven't explicitly described a recursive pattern for yet. Consider the following problem:
I want to go up a flight of stairs that has
nsteps. I can either take 1 or 2 steps each time. How many different ways can I go up this flight of stairs?
For example, in the case where
n is 5, there are 8 possible ways:
In order to solve this problem, we have to introduce a pattern called Tree Recursion. Tree Recursion is just a phrase to describe when you make a recursive call more than once in your recursive case. Why would we need to do this here? Consider one solution to the above problem:
(define (count-stairs n) (cond [(= n 1) 1] [(= n 2) 2] [else (+ (count-stairs (- n 1)) (count-stairs (- n 2)) ]) ))
Breaking the procedure down, there are three parts to consider
count-stairs is tree recursive because whenever it is called, the recursive calls branches out and form an upside-down tree. For example,
Let consider a harder problem to solve:
How many different ways can we make change of $1.00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a function to compute the number of ways to change any given amount of money using any set of currency denominations?
We approach the problem in a similar fashion as above. By thinking carefully about the problem statement, we can notice that we have to keep track of a two things: what our amount currently is, and which coins we have to use (we can keep track of this in a sentence, e.g.
'(50 25 10 5 1)). From there, we can observe a few things about our base cases:
For the recursive case, we again have to make two recursive calls. These two recursive calls break our problem into two worlds:
(50 25 10 5 1))
(25 10 5 1).
When we translate this into code, we get the following:
(define (count-change amount) (cc amount `(50 25 10 5 1))) (define (cc amount kinds-of-coins) (cond [(= amount 0) 1] [(or (< amount 0) (empty? kinds-of-coins)) 0] [else (+ (cc amount (bf kinds-of-coins)) (cc (- amount (first kinds-of-coins)) kinds-of-coins))] ))
Tree recursive procedures typically take exponential time to compute. Why would we ever use them?