MÔ PHỎNG DÃY FIBONACCI DÙNG ĐỆ QUY

Fibonacci bằng Đệ quy (Recursion)

F(n) = F(n−1) + F(n−2), với F(0)=0, F(1)=1

Nhấn "Bắt đầu" để xem quá trình đệ quy

Điều khiển

Giá trị n:

Trạng thái hiện tại

Bước: 0

Đang xử lý: -

Kết quả: -

Tóm tắt

Công thức: F(n)=F(n−1)+F(n−2)

Cơ sở: F(0)=0, F(1)=1

Độ phức tạp: ~O(φⁿ)

Tối ưu: Dùng memoization/DP

Dãy số Fibonacci

0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

Code Python

# Fibonacci đệ quy đơn giản
def fibonacci(n):
    # Điều kiện cơ sở
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # Gọi đệ quy
    return fibonacci(n - 1) + fibonacci(n - 2)

# Sử dụng
n = 5
print(f"F({n}) = {fibonacci(n)}")

# Tối ưu với Memoization
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]