Chương trình Python tìm số hạng thứ n của dãy Fibonacci bằng đệ quy

Cho số nguyên n. Tìm số Fibonacci thứ n (bắt đầu từ 0: F₁=0, F₂=1, F₃=1, F₄=2...). Sử dụng hàm đệ quy đơn giản.

Ví dụ: n = 8 → 13.

Đệ quy

• Cơ sở: n <= 2 trả về n - 1.
• Đệ quy: solve(n-1) + solve(n-2).

Lưu ý: Đệ quy thuần túy có độ phức tạp 지수, chỉ phù hợp cho n nhỏ. Với n lớn nên dùng memoization hoặc lặp.

Ví dụ mã nguồn

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

n = 8
print(solve(n))  # 13

Đầu vào / Đầu ra

Input:  8
Output: 13