Mô phỏng thuật toán Cây đệ quy Fibonacci

Fibonacci Recursion Tree · Nhóm: Đệ quy

Vẽ cây gọi hàm của fib(n) đệ quy trần để thấy mỗi lời gọi tách thành fib(n−1) và fib(n−2), và nhiều bài con bị tính lặp lại.

Ý tưởng

Mỗi nút là một lời gọi fib(đối số); nút lá là ca cơ sở fib(0)=0 và fib(1)=1.

Đánh giá theo hậu thứ tự: tính hai con trước rồi cộng lại để có giá trị của nút.

Đếm số lời gọi và chỉ ra fib(2), fib(1)… xuất hiện nhiều lần ở các nhánh khác nhau.

Vì sao đúng

Đệ quy trần không nhớ kết quả, nên cùng một bài con bị tính lại ở mỗi nhánh; số lời gọi phình theo φⁿ. Đây chính là động lực để dùng ghi nhớ (memoization) hay quy hoạch động, mỗi bài con chỉ tính một lần.

Mã Python

def fib(n):
    if n < 2:
        return n          # base case fib(0)=0, fib(1)=1
    return fib(n - 1) + fib(n - 2)

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.