Hiểu đệ quy với Fibonacci Series

Question

Tôi đang cố gắng hiểu rõ hơn về đệ quy và cách báo cáo trả về hoạt động. Như vậy, tôi đang xem xét một đoạn mã có nghĩa là để xác định số lượng mã số liên kết với một thuật ngữ nhất định - trong trường hợp này, 4. Tôi gặp khó khăn khi hiểu được câu lệnh khác.

def f(n): 
    if n == 0: 
    return 0 
    if n == 1: 
    return 1 
    else: 
    return f(n-1) + f(n-2) 

f(4) 

Tôi đã thử sử dụng Visualize Python để kiểm tra những gì xảy ra ở mỗi bước, nhưng tôi bị lạc khi nó chạm vào câu lệnh khác.

Có vẻ như nó đang lấy giá trị của n và trừ 1, để tạo giá trị n mới 3 mà nó trả về định nghĩa hàm. Vì vậy, nó dường như chỉ trả về giá trị từ hàm đầu tiên trong câu lệnh khác. Tuy nhiên, câu lệnh khác được viết để trả về tổng của 2 hàm f (n-1) + f (n-2), trong trường hợp nào tôi nghĩ giá trị trả về sẽ là 5? Thậm chí bạn có thể thêm 2 chức năng cùng nhau không?

Cảm ơn trước sự giúp đỡ của bạn.

Đây là một liên kết đến mã trong Hình dung Python Sum of 2 functions

Answer 1

Khi nghi ngờ, chỉ cần phá vỡ nó xuống.

dòng chảy Cây thực sự là phản trực giác để kiểm soát dòng chảy thực tế, nhưng một khi bạn hiểu được chuỗi các cuộc gọi, nó trở nên rõ ràng hơn. Điều cần hiểu ở đây là bạn tiếp tục phá vỡ một tính toán lớn hơn cho một tổng các tính toán nhỏ hơn, và bạn dừng lại khi bạn nhấn trường hợp cơ bản (các câu lệnh if). Bây giờ bạn có thể thực hiện tất cả các tính toán nhỏ và kết hợp các kết quả của những tính toán nhỏ này để tạo thành một kết quả lớn hơn, lớn hơn, cho đến khi bạn có câu trả lời cuối cùng.

Mỗi khi một cuộc gọi đệ quy chạm vào vỏ cơ sở, nó sẽ trả về 1, hoặc 0, tùy thuộc vào trường hợp nào bị trúng. Giá trị này sẽ được trả lại cho người gọi trước đó. Để hiểu, hãy xem xét:

f(1)3 + f(0)3

Lưu ý rằng chỉ số này thể hiện độ sâu của cây gọi đệ quy. Cuộc gọi được thực hiện bởi f(2)2. f(1)3 được tính trước, và 1 được trả về f(2)2. f(0)3 sau đó được tính và 0 được trả về f(2)2. Hai giá trị trả về được tổng kết và kết quả là 1.

f(2)2 sau đó lợi nhuận1 để bất cứ ai gọi nó, mà trong trường hợp này xảy ra là f(3)1. f(3)1 được gọi là f(2)2 + f(1)2, trong khi điều này f(1)2 khác cũng trả về 1 đến f(3)1, người hiện thêm rằng với kết quả là f(2)2, để tạo thành 2.

f(3)1 nay đi 2-f(4)0, người gọi của nó, mà đã xảy ra để gọi f(3)1 + f(2)1 ... và vì vậy nó đi.

---

Một cách khác để nhìn vào điều này là bắt đầu từ lời gọi hàm đầu tiên được thực sự thực hiện: f(4)0.

f(4)0 tính f(3)1 + f(2)1. Nhưng để tính toán f(3)1, cần biết f(2)2 + f(1)2 và tương tự, để tính f(2)1, cần biết f(1)2 + f(0)2, v.v.

Answer 2

Thêm một số báo cáo in cũng có thể giúp làm rõ trình tự:

def f(n): 
    print("Number received:", n) 
    if n == 0: 
     return 0 
    if n == 1: 
     return 1 
    else: 
     print("---- First recursion ----") 
     a = f(n-1) 
     print("---- Second recursion ----") 
     b = f(n-2) 
     print(" a=:",a,"; b=",b,"; returning:", a+b) 
     return a + b 

print("Final f(4)=", f(4)) 

Output:

Number received: 4 
---- First recursion ---- 
Number received: 3 
---- First recursion ---- 
Number received: 2 
---- First recursion ---- 
Number received: 1 
---- Second recursion ---- 
Number received: 0 
a=: 1 ; b= 0 ; returning: 1 
---- Second recursion ---- 
Number received: 1 
a=: 1 ; b= 1 ; returning: 2 
---- Second recursion ---- 
Number received: 2 
---- First recursion ---- 
Number received: 1 
---- Second recursion ---- 
Number received: 0 
a=: 1 ; b= 0 ; returning: 1 
a=: 2 ; b= 1 ; returning: 3 
Final f(4)= 3