CODEWITHSUNDEEP
recursionlispbinary-treesicp
Zakaria Sichaib
Zakaria Sichaib

Reputation: 137

Can't understand this Tree recursion problem

So i'm going through the SICP book. I'm in the tree recursion chapter. I googled tree recursion to gain more knowledge about it and i stumbled upon this exercice and i'm having hard times to understand it perfectly.

Exercice :

I want to go up a flight of stairs that has n steps. I can either take 1 or 2 steps each time. How many different ways can I go up this flight of stairs?

The answer was :

For example, in the case where nis 5, there are 8 possible ways:

1 1 1 1 1

2 1 1 1

1 2 1 1

1 1 2 1

1 1 1 2

1 2 2

2 1 2

2 2 1

And this the code block i had trouble understanding it fully :

(define (count-stairs n)
  (cond [(= n 1) 1]
        [(= n 2) 2]
        [else (+ (count-stairs (- n 1))
                 (count-stairs (- n 2)) ]) ))

The image illustrating the process

enter image description here

My problem is , why is there the + sign? isn't the count-stairs(4) + count-stairs(3) result in 7 steps? or i'm missing something here

ALSO: here's the full link to the exercice https://berkeley-cs61as.github.io/textbook/tree-recursion.html

please need your help !

Upvotes: 0

Views: 123

Answers (1)

Kaz
Kaz

Reputation: 58588

The tree diagram is just giving the space of function calls and their arguments that occur starting with (count-stairs 5). When we call the function with argument 5, it will call (count-stairs 4) due to the expression (count-stairs (- n 1)) and it will call (count-stairs 3) due to the expression (count-stairs (- n 2)). Of course, these values get added with + which becomes the return value of the call. The tree just doesn't show that return value information, just the call arguments.

(count-stairs 5) doesn't mean "count five stairs", but "call the count-stairs function with argument 5 to calculate how many different ways there are to go up a flight of 5 stairs".

For (count-stairs 3) the result will be 3, because (count-stairs 1) and (count-stairs 2) just return 1 and 2, respectively.

However, (count-stairs 4) adds (count-stairs 3) and (count-stairs 2), therefore (count-stairs 4) -> 5.

We can use this arrow notation to annotate the expressions in the tree with their result values, starting from the bottom and working upward. At the top of the tree we will end up with (count-stairs 5) -> 8.

count-stairs is just a slight variation of the recursive Fibonacci function in disguise.

Why does this calculate the number of ways of ascending the stairs using 1 or 2 sized steps? Firstly, the base cases are clear. If a staircase has one step, there is only one way to traverse it: we take that one step. So (count-stairs 1) -> 1. If there are two steps, then then there are two ways: take each step, or take both of them in one stride. Thus (count-stairs 2) -> 2. Then comes the tricky inductive part. If we are faced with three or more stairs, what is the solution?

If we are faced with a staircase with n steps, n > 2, then we have two possibilities about how to begin climbing. Possibility (1): we can take one step, and then climb the remaining staircase of n - 1 steps; or, possibility (2) we can take two steps as a single stride, and then climb the remaining staircase of n - 2 steps. Thus the number of ways of climbing n steps is the sum of the ways from these two possibilities: the number of ways of climbing n - 1 steps, plus the number of ways of climbing n - 2 steps.

Upvotes: 2

Related Questions