پایتون

جلسه ۲۶: Recursion در پایتون

در این درس به جنبه های موضوع بازگشت یا Recursionدر پایتون میپردازیم.

تعریف

Recursion یعنی اینکه ما یک تابع را درون خودش دوباره فرخوانی کنیم و اجرا بشود. هر فراخوانی recursive باعث میشود یک Scope درون تابع داخل تر برویم.

فراخوانی های بازگشتی، در حالتی به اسم حالت پایه متوقف میشوند. حالت پایه یک آزمون است، که برای نشان دادن اینکه دیگر هیچ بازگشتی وجود ندارد، استفاده میشود.

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

در شکل‌های بالا میبینید که یک تابع به تعداد مشخص مرتبا فراخوانی میشود.

یک مثال ساده

حال یک برنامه‌ای مینویسیم که یک عدد را مرتبا یکی کم کند تا زمانی که به صفر برسد.

def rec_count(number):
    print(number)
    # Base case
    if number == 0:
        return 0
    rec_count(number - 1)  # A recursive call with a different argument
    print(number)


rec_count(5)

درک این موضوع نسبتا آسان است.

در هر فراخوانی مقدار متغیر number چاپ میگردد. سپس ما چک میکنیم که حالت پایه ما آیا اتفاق افتاده است یانه. اگر جواب نه بود، دوباره تابع را فراخوانی میکنیم اما اینبار با ورودی یکی کمتر از قبلی.

یک نکته مهم هم وجود دارد اینکه یک فراخوانی بیرونی، عملی انجام نمیدهد تا زمانی که فراخوانی درونی به اتمام برسد. به همین دلیل هم هست که توالی ما از ۵ تا ۰ و دوباره از ۰ تا ۵ اتفاق افتاده است.

چرا از Recursion استفاده کنیم؟

Recursive مفهومی است که درک آن در ابتدا میتواند مشکل باشد.اما مزایای خودش را هم دارد. برای شروع این روش میتواند زمان اجرای یکسری الگوریتم‌ها را کاهش دهد که باعث میشود کدهای شما کارایی بالاتری داشته باشد.

recursive ها این امکان را به ما میدهند تا مسائلی نظیر، گراف ها و درخت ها را حل کنیم اینها مسائلی هستند که در آینده آن ها را یاد خواهیم گرفت. این روش در الگوریتم های جستوجو نیز بسیار با اهمیت هستند.

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

یک مثال پیچیده

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

۰ ۱ ۱ ۲ ۳ ۵ ۸ ۱۳

حال یک کدی را مینویسیم که ورودی ‌ای به نام n را میگیرد و nامین عضو یک دنباله فیبوناچی را محاسبه میکند. این نکته هم مهم است که در مثال پیش رو اگر ورودی کمتر از ۱ باشد محاسبه ‌ای انجام نمیشود. پس ورودی ما بزرگتر از ۱ خواهد بود. بنابراین اگر n=6 انتخاب شد، این تابع خروجی ۵ را به ما میدهد.

def fib(n):
    # The base cases
    if n <= 1:  # First number in the sequence
        return 0
    elif n == 2:  # Second number in the sequence
        return 1
    else:
        # Recursive call
        return fib(n - 1) + fib(n - 2)


print(fib(6))

اول از همه ما حالت پایه خودمان را مشخص میکنیم. میدانیم که دو مقدار اول همیشه ۰ و ۱ هستند بنابراین اینجا جاییست که میتوان بازگشت را متوقف کرد و این جا به عنوان حالت پایه در نظر گرفته میشود.

اگر n از ۲ بزرگتر باشد، این تابع باید دو مقدار ماقبل n را محاسبه کند.

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

در بخش بعدی به بررسی loop ها در پایتون میپردازیم. اما قبل از آن کوییز های مربوط به این بخش را انجام دهید.

نوشته های مشابه

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

دکمه بازگشت به بالا