کـاتـالـیـز

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

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

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

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

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

در این روش، تابع با استفاده از بازگشت (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)استفاده کرد.