بازگشت در

درباره‌ی بازگشت

«بازگشت» روشی است برای اجرای مکرر کد درون یک تابع، از طریق فراخوانی خودِ تابع. توابعی که خودشان را فراخوانی می‌کنند، توابع بازگشتی نامیده می‌شوند. بازگشت را می‌توان روشی دیگر برای حلقه زدن/تکرار دانست. و مانند حلقه زدن، از یک عبارت «منطقی» یا آزمون True/False استفاده می‌شود تا مشخص شود چه زمانی اجرای بازگشتی متوقف شود.

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

حلقه زدن در برابر پیاده‌سازی بازگشتی

حلقه زدن و بازگشت ممکن است از این جهت که هر دو تکراری‌اند، به نظر مشابه بیایند. با این حال، هم در سطح کد و هم در سطح پیاده‌سازی، شکل‌شان متفاوت است. حلقه زدن می‌تواند در همان قالب روی پشته‌ی فراخوانی انجام شود. این کار معمولاً با به‌روزرسانی مقدار یک یا چند متغیر مدیریت می‌شود تا وضعیت برای هر تکرار به‌تدریج حفظ شود. این پیاده‌سازی کارآمدی است، اما هنگام نگاه کردن به کد می‌تواند تا حدی شلوغ باشد.

بازگشت، به‌جای به‌روزرسانی وضعیت متغیر، می‌تواند مقادیر به‌روزشده را مستقیماً به‌عنوان آرگومان به فراخوانی بعدی (تکرار بعدی) همان تابع بفرستد. این کار بدنه‌ی تابع را مرتب‌تر می‌کند و می‌تواند روشن کند که هر به‌روزرسانی چگونه رخ می‌دهد. با این حال، پیاده‌سازی کم‌کارآمدتری هم هست، چون هر فراخوانی همان تابع قالب دیگری به پشته اضافه می‌کند.

بازگشت: چرا و چرا نه؟

اگر خطر ایجاد خطا یا سرریز پشته وجود دارد، چرا کسی باید از راهبرد بازگشتی برای حل مسئله استفاده کند؟ خوانایی، قابلیت ردیابی، و هدف. ممکن است موقعیت‌هایی پیش بیاید که یک راه‌حل وقتی با بازگشت بیان می‌شود، خواناتر و/یا استدلال درباره‌اش آسان‌تر باشد تا وقتی با حلقه زدن بیان می‌شود. همچنین ممکن است محدودیت‌های برنامه‌ای در استفاده یا تغییر داده‌ها، مدیریت پیچیدگی، واگذاری مسئولیت، یا سازمان‌دهی حجم کار وجود داشته باشد.

مسائلی که برای بازگشت مناسب‌اند شامل مسائل پیچیده اما تکراری است که به‌مرور کوچک‌تر می‌شوند، به‌ویژه الگوریتم‌های تقسیم و غلبه و الگوریتم‌های انباشتی. با این حال، به‌دلیل محدودیت پایتون در تعداد قالب‌های مجاز روی پشته، همه‌ی مسائل از یک راهبرد کاملاً بازگشتی بهره نمی‌برند. مسائلی که کم‌تر به‌طور طبیعی با بازگشت سازگارند شامل مسائلی است که وضعیت پایداری دارند اما باید برای تعداد مشخصی چرخه تکرار شوند، مسائلی که باید ناهمگام اجرا شوند، و موقعیت‌هایی که به تعداد زیادی تکرار نیاز دارند.

راهبرد حلقه زدن در برابر بازگشتی: نگرانی ایندیرا

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

آدیا که تازه در حال یادگیری برنامه‌نویسی با پایتون است، برنامه‌ای بر اساس نخستین ایده‌هایش می‌نویسد. او می‌خواهد یک list از تاریخ‌های واریز برگرداند تا بتوان آن‌ها را چاپ کرد. او می‌خواهد تابعی بنویسد که برای هر سالی کار کند. در صورتی که زمان‌بندی تغییر کند (یا اگر بستگان دیگری بخواهند آدیا زمان‌بندی واریزهایشان را محاسبه کند)، او تصمیم می‌گیرد که تابع باید پارامتر دیگری برای روز هفته بگیرد. سرانجام، آدیا تصمیم می‌گیرد که تابع به پارامتری نیاز دارد که مشخص کند کدام روز هفته از ماه است: اول، دوم و غیره. برای همه‌ی این نیازها، او تصمیم می‌گیرد از کلاس date که از datetime وارد شده استفاده کند. با کنار هم گذاشتن همه‌ی این‌ها، آدیا به این می‌رسد:

from datetime import date


def paydates_for_year(year, weekday, ordinal):
    """Returns a list of the matching weekday dates.
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    output = []

    for month in range(1, 13):
        for day_num in range(1, 8):
            if date(year, month, day_num).isoweekday() == weekday:
                output.append(date(year, month, day_num + (ordinal - 1) * 7))
                break
    return output

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year(2022, 3, 2))

این نخستین تکرار کار می‌کند، اما آدیا می‌پرسد آیا می‌تواند کد را بازنویسی کند تا از خطوط کم‌تر و حلقه‌های تودرتوی کم‌تری استفاده کند. او همچنین خوانده است که کمینه کردن تغییر وضعیت کار خوبی است، پس می‌خواهد ببیند آیا می‌تواند از تغییر دادن برخی از متغیرهایش مانند output، month و day_num پرهیز کند.

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

from datetime import date


def paydates_for_year_rec(year, weekday, ordinal, month, day_num, output):
    """Returns a list of the matching weekday dates
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
        month (int): The month number currently being processed.
        day_num (int): The day number of the month currently being processed.
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    if month == 13:
        return output
        
    if date(year, month, day_num).isoweekday() == weekday:
        return paydates_for_year_rec(
                 year, weekday, ordinal, month + 1, 1, output
                 + [date(year, month, day_num + (ordinal - 1) * 7)]
                 )
    
    return paydates_for_year_rec(year, weekday, ordinal, month, day_num + 1, output)

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year_rec(2022, 3, 2, 1, 1, []))

آدیا خوشحال است که دیگر حلقه‌ی تودرتویی نیست، وضعیتی تغییر نمی‌کند، و کد ۲ خط کم‌تر دارد!

او کمی نگران است که رویکرد بازگشتی گام‌های بیشتری از رویکرد حلقه‌ای مصرف می‌کند و بنابراین کارایی کم‌تری دارد. اما بازنویسی مسئله با بازگشت قطعاً به او کمک کرده تا با حلقه‌های تودرتوی زشت (یک خطر کارایی)، تغییر گسترده‌ی وضعیت، و سردرگمی پیرامون منطق شرطی پیچیده کنار بیاید. احساس می‌شود خواناتر هم هست. او مطمئن است که وقتی پس از مدتی به این کد بازمی‌گردد، می‌تواند راحت‌تر آن را بخواند و به یاد بیاورد که چه کاری انجام می‌دهد.

در آینده، آدیا ممکن است ابتدا تلاش کند مسائل را به‌صورت بازگشتی حل کند. ممکن است برایش آسان‌تر باشد که در ابتدا مسئله را در گام‌های روشن بپیماید، وقتی که تودرتویی، تغییر، و پیچیدگی کمینه شده‌اند. پس از پی بردن به منطق پایه، می‌تواند بر بهینه‌سازی گام‌های بازگشتی اولیه‌اش به یک رویکرد حلقه‌ای کارآتر تمرکز کند.

حتی بعدتر، وقتی درباره‌ی tuples یاد می‌گیرد، آدیا می‌تواند رویکردهای «بهینه‌سازی» بیشتری را در نظر بگیرد، مانند استفاده از list comprehension همراه با Calendar.itermonthdates، یا memoizing مقادیر مشخصی.

گونه‌ی بازگشتی: فراخوانی دنباله‌ای

فراخوانی دنباله‌ای زمانی است که آخرین دستور یک تابع تنها خودش را فراخوانی کند و بس. این مثال فراخوانی دنباله‌ای نیست، چون تابع به نتیجه‌ی فراخوانی خودش ۱ اضافه می‌کند:

def print_increment(step, max_value):
    if step > max_value:
        return 1
    print(f'The step is {step}')
    return 1 + print_increment(step + 1, max_value)


def main():
    retval = print_increment(1, 2)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

این خروجی را چاپ می‌کند:

The step is 1
The step is 2
retval is 3 after recursion

برای بازنویسی آن به یک فراخوانی دنباله‌ای، retval را پارامتری از print_increment کنید.

def print_increment(step, max_value, retval):
    if step > max_value:
        return retval
    print(f'The step is {step}')
    return print_increment(step + 1, max_value, retval + 1)


def main():
    retval = print_increment(1, 2, 1)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

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

محدودیت‌های بازگشت در پایتون

برخی زبان‌ها می‌توانند فراخوانی‌های دنباله‌ای را بهینه کنند تا هر فراخوانی بازگشتی از قالب پشته نخستین فراخوانی تابع دوباره استفاده کند (مشابه روشی که یک حلقه از یک قالب دوباره استفاده می‌کند)، به‌جای اینکه قالب دیگری به پشته اضافه کند. پایتون یکی از آن زبان‌ها نیست. برای محافظت در برابر سرریز پشته، پایتون محدودیتی برای بازگشت دارد که به‌طور پیش‌فرض هزار قالب است. هنگامی که مفسر تشخیص دهد محدودیت بازگشت نقض شده است، یک استثنای RecursionError صادر می‌شود. می‌توان از متد sys.setrecursionlimit برای افزایش محدودیت بازگشت استفاده کرد، اما این کار خطر یک خطای قطعه‌بندی زمان اجرا را به همراه دارد که برنامه و احتمالاً سیستم‌عامل را از کار می‌اندازد.

منابع

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

• python-programming: recursion
• Real Python: python-recursion
• Real Python: python-thinking-recursively