Đệ quy trên Fibonacci Sequence

Question

Tôi cần một số trợ giúp để hiểu được quá trình xử lý xảy ra ở đây, vì vậy hãy nói rằng tôi gọi số fib(5) Tôi muốn mã 5, tức là 8. Nhưng bộ não của tôi đang cố gắng hiểu thuật toán cho biết không phải. Đây là cách tôi (sai) nghĩ:

return fib(4) + fib(3) // Stack frame 1 
return fib(3) + fib(1) // Stack frame 2 

nay gây ra x là 1 fib(1), tuyên bố có điều kiện if x == 0 or x == 1: làm cho đệ quy kết thúc. Theo logic của tôi sẽ trở thành 3 + 1 + 4 + 3. Vui lòng sửa lỗi logic của tôi.

def fib(x): 
    """assumes x an int >= 0 
     returns Fibonacci of x""" 
    assert type(x) == int and x >= 0 
    if x == 0 or x == 1: 
     return 1 
    else: 
     return fib(x-1) + fib(x-2) 

Answer 1

Đây là sự mở rộng đầy đủ về những gì sẽ xảy ra:

fib(5) expands to fib(4)+fib(3) 
    fib(4) expands to fib(3)+fib(2) 
    fib(3) expands to fib(2)+fib(1) 
     fib(2) expands to fib(1)+fib(0) 
     fib(1) evaluates to 1 
     fib(0) evaluates to 1 
     fib(1) evaluates to 1 
    fib(2) expands to fib(1)+fib(0) 
     fib(1) evaluates to 1 
     fib(0) evaluates to 1 
    fib(3) expands to fib(2)+fib(1) 
    fib(2) expands to fib(1)+fib(0) 
     fib(1) evaluates to 1 
     fib(0) evaluates to 1 
    fib(1) evaluates to 1 

Nếu bạn đếm những người thân, bạn sẽ có được 8 là câu trả lời.

Answer 2

Đối với tất cả x lớn hơn 1, các fib chức năng tự gọi mình hai lần:

1. fib(5) trở thành fib(4) + fib(3)
2. và mở rộng để (fib(3) + fib(2)) + (fib(2) + fib(1))
3. và mở rộng để ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + 1)
4. mở rộng để (((fib(1) + fib(0)) + 1) + (1 + 1)) + ((1 + 1) + 1)
5. mở rộng đến (((1 + 1) + 1) + (1 + 1)) + ((1 + 1) + 1)

có tổng cộng là 8.