۱. معرفی دنباله فیبوناچی

دنباله فیبوناچی یک سری از اعداد است که هر عدد از جمع دو عدد قبلی خود حاصل می‌شود. این دنباله با دو مقدار اولیه ۰ و ۱ شروع می‌شود و فرمول آن به‌صورت زیر است:

F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)

با فرض اینکه:

F(0)=0,F(1)=1F(0) = 0, \quad F(1) = 1

به‌عنوان مثال، چند عدد اول این دنباله عبارتند از:

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

۲. شِرط پایه (Base Case) و قدم بازگشتی (Recursive Step)

در تعریف بازگشتی دنباله فیبوناچی، شِرط پایه شامل دو مقدار اول آن است:

  • F(0) = 0

  • F(1) = 1

قدم بازگشتی به‌صورت:

  • F(n) = F(n-1) + F(n-2) برای n ≥ 2

۳. پیاده‌سازی بازگشتی دنباله فیبوناچی در پایتون

در این روش، تابع با استفاده از بازگشت (Recursion) مقدار عدد فیبوناچی را برای مقدار n محاسبه می‌کند.

python

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

# اجرای برنامه
n = 10
print(f"عدد {n}ام از دنباله فیبوناچی: {fibonacci_recursive(n)}")

📌 مشکل این روش: اجرای آن برای n‌های بزرگ بسیار کند است زیرا محاسبات تکراری زیادی انجام می‌شود.

۴. بهینه‌سازی با استفاده از Memoization

برای حل مشکل محاسبات تکراری، می‌توان از ذخیره‌سازی نتایج قبلی (Memoization) استفاده کرد:

python

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_memoized(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_memoized(n - 1) + fibonacci_memoized(n - 2)

# اجرای برنامه
print(f"عدد 30ام از دنباله فیبوناچی: {fibonacci_memoized(30)}")

این روش باعث کاهش چشمگیر زمان اجرا می‌شود.

۵. روش بهینه‌تر با استفاده از روش غیر بازگشتی (Iterative)

روش تکراری برای محاسبه سریع‌تر دنباله فیبوناچی:

python

def fibonacci_iterative(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

# اجرای برنامه
print(f"عدد 50ام از دنباله فیبوناچی: {fibonacci_iterative(50)}")

📌 مزیت این روش: بسیار سریع‌تر از روش بازگشتی و مصرف کمتر حافظه.

نتیجه‌گیری

دنباله فیبوناچی یک مفهوم مهم در ریاضیات و علوم کامپیوتر است که کاربردهای زیادی در الگوریتم‌ها، رمزنگاری، گرافیک کامپیوتری و حتی طبیعت دارد. بسته به نیاز، می‌توان از روش‌های بازگشتی، ذخیره‌سازی نتایج (Memoization) یا روش تکراری (Iterative) استفاده کرد.