如何解释用于计算到达第n个楼梯的方式的代码？

Question

我正在尝试从geeksforgeeks解释此代码：

def fib(n): 
    if n <= 1: 
        return n 
    return fib(n-1) + fib(n-2) 

def countWays(s): 
    return fib(s + 1) 

s = 4
print "Number of ways = ", 
print countWays(s) 

当我将数字代入函数时，我似乎无法获得正确的答案。这是我的思考过程：

def countWays(s): 
    return fib(4 + 1) #5

#this goes into fib(n). 5 is not less than or equal to n so I skip to the else statement:

fib(5-1) + fib(5-2) 

#fib(4) + fib(3) since these are still not less than or equal to n I input 
#them into the function again.

 fib(4-1) + fib(3-2) 

#fib(3) + fib(1) now that one of the n is less than or equal to n, 
#I return n and get 4 (3+1). The answer is supposed to be 5.

Answer 1

像这样检查出来：

# Python 3
def fib(n): 
    print(f'Fib: {n}')
    if n <= 1:
        print('End')
        return n
    else:
        print(f'Send: {n-1} and {n-2}')
    return fib(n-1) + fib(n-2) 

def countWays(s): 
    return fib(s + 1) 

s = 4
print("Number of ways = ")
print(countWays(s))

Fib: 5           # A
Send: 4 and 3    # A.B and A.C
Fib: 4           # A.B
Send: 3 and 2    # A.B.1 and A.B.2
Fib: 3           # A.B.1
Send: 2 and 1    # A.B.1.1 and A.B.1.2
Fib: 2           # A.B.1.1
Send: 1 and 0    # A.B.1.1.1 and A.B.1.1.2
Fib: 1           # A.B.1.1.1
End              # (END) A.B.1.1.1       -> 1
Fib: 0           # A.B.1.1.2
End              # (END) A.B.1.1.2       -> 0
Fib: 1           # A.B.1.2
End              # (END) A.B.1.2         -> 1
Fib: 2           # A.B.2
Send: 1 and 0    # A.B.2.1 and A.B.2.2
Fib: 1           # A.B.2.1
End              # (END) A.B.2.1         -> 1
Fib: 0           # A.B.2.2
End              # (END) A.B.2.2         -> 0
Fib: 3           # A.C
Send: 2 and 1    # A.C.1 and A.C.2
Fib: 2           # A.C.1
Send: 1 and 0    # A.C.1.1 and A.C.1.2
Fib: 1           # A.C.1.1
End              # (END) A.C.1.1         -> 1
Fib: 0           # A.C.1.2
End              # (END) A.C.1.2         -> 0
Fib: 1           # A.C.2
End              # (END) A.C.2           -> 1
5                                     # 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1