برنامه فیبوناچی با تابع بازگشتی در پایتون

در این تمرین قصد داریم برنامه فیبوناچی با تابع بازگشتی در پایتون را بررسی و پیاده سازی نماییم.

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

مثال:

0 1 1 2 3 5 8 13 21

اگر کاربر عدد 5 را وارد کند منظورش جایگاه پنجم در سری فیبوناچی میباشد پس عدد 5 به عنوان خروجی چاپ میشود.

نکته: عدد صفر را به عنوان جایگاه در نظر نگیرید.

ویدیو حل تمرین را مشاهده نمایید.

الگوریتم برنامه فیبوناچی چیست؟

کد فیبوناچی بازگشتی، یک الگوریتم برنامه نویسی است که از طریق تابع بازگشتی، برای محاسبه‌ی اعداد فیبوناچی استفاده می‌شود.

این اعداد به صورت دنباله‌ای از اعداد طبیعی است که با عدد ۰ و ۱ شروع می‌شود و هر عضو بعدی آن، مجموع دو عضو قبلی آن است.

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

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

حالت پایه‌ی این تابع، محاسبه‌ی اولین دو عضو دنباله است که برابر با ۰ و ۱ است.

سپس تابع به صورت بازگشتی، با استفاده از دو عضو قبلی، عضو بعدی دنباله را محاسبه می‌کند.

بیشتر بخوانید:پخش صدا در tkinter پایتون

سورس کد برنامه فیبوناچی پایتون

برای نوشتن کد فیبوناچی بازگشتی، می‌توانید از دو پارامتر ورودی، یعنی n و m استفاده کنید.

n، عددی است که ما می‌خواهیم عضو فیبوناچی آن را محاسبه کنیم و m هم نشان‌دهنده‌ی عضو بعدی در دنباله است که با استفاده از آن، می‌توان عضو n+1 را محاسبه کرد.

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

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

ابتدا چک می‌شود که آیا عدد مورد نظر برابر با ۰ یا ۱ است یا نه؛ در صورتی که برابر با یکی از این دو باشد، مقدار متناظر با آن را برمی‌گردانیم.

در غیر این صورت، با استفاده از تابع بازگشتی، مقدار دو عضو قبلی را جمع کرده و عضو بعدی دنباله‌ی فیبوناچی را محاسبه می‌کنیم.

به عنوان مثال، برای محاسبه‌ی عضو پنجم دنباله‌ی فیبوناچی، کافی است کد زیر را اجرا کد:

print(fibonacci_recursive(5, 2))

برنامه فیبوناچی با یک ورودی

حالا فرض کنید این برنامه را با یک ورودی یعنی فقط دریافت جایگاه سری میخواهیم بنویسیم.

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

در این کد، تابع بازگشتی فیبوناچی با یک ورودی به نام n پیاده‌سازی شده است.

همانطور که در کد قبلی نیز دیدید، اگر n برابر با ۰ یا ۱ باشد، مقدار متناظر با آن را برمی‌گردانیم.

در غیر این صورت، با استفاده از تابع بازگشتی، مقدار دو عضو قبلی را جمع کرده و عضو بعدی دنباله‌ی فیبوناچی را محاسبه می‌کنیم.

برای محاسبه‌ی عضو n ام دنباله‌ی فیبوناچی، کافی است کد زیر را اجرا کنید:

n = 5
print(fibonacci_recursive(n))

در این مثال، عدد ۵ به عنوان ورودی به تابع fibonacci_recursive پاس میدهیم.

خروجی این کد برابر با ۵ است که مقدار عضو پنجم دنباله‌ی فیبوناچی است.

برنامه فیبوناچی برای نمایش کل سری فیبوناچی

می‌توانید کد فیبوناچی را به گونه‌ای پیاده‌سازی کنید که کل دنباله‌ی فیبوناچی تا یک عدد مشخص را چاپ کند.

برای این کار، می‌توانید از یک حلقه for استفاده کنید و برای هر عدد از دنباله‌ی فیبوناچی تا ن امین عضو، مقدار آن را چاپ کنید.

در کد زیر، یک تابع با نام fibonacci_series به شما نشان داده شده است که کل دنباله‌ی فیبوناچی تا یک عدد مشخص را چاپ می‌کند:

در این کد، یک لیست خالی به نام series ایجاد میشود.

سپس با استفاده از حلقه for، برای هر عدد از دنباله‌ی فیبوناچی تا عدد n، مقدار آن را محاسبه کرده و به لیست series اضافه می‌کنیم.

در نهایت، لیست series با استفاده از دستور print چاپ می‌شود.

برای مثال، اگر عدد ۱۰ را به عنوان ورودی به تابع fibonacci_series بدهیم، خروجی کد برابر با [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] خواهد بود که مقدار کل دنباله‌ی فیبوناچی تا عدد ۱۰ است.

تمرین های با جواب پایتون