بازگشتی

تا اینجا تابع‌ها همدیگر را صدا می‌زدند. اما یک حالت خاص و قدرتمند وجود دارد: تابعی که خودش را صدا می‌زند. به این تکنیک می‌گویند بازگشتی (Recursion). در نگاه اول دور خودش چرخیدن به نظر می‌رسد، ولی با یک قاعده ساده مهار می‌شود و برای مسئله‌های شاخه‌شاخه، طبیعی‌ترین ابزار دنیاست.

دو جزء همیشگی: حالت پایه و گام بازگشتی

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

def countdown(n):
    if n == 0:
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)

countdown(3)

هر تابع بازگشتی درست، دقیقاً دو جزء دارد:

• حالت پایه (Base Case) — وضعیتی که دیگر خودش را صدا نمی‌زند؛ اینجا n == 0 است. بدون آن، فراخوانی تا ابد ادامه می‌یافت.
• گام بازگشتی (Recursive Step) — فراخوانی دوباره با مسئله‌ای کوچک‌تر؛ اینجا countdown(n - 1) است. هر دور باید به سمت حالت پایه نزدیک شود.

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

بازگشتی محاسباتی؛ فاکتوریل

فاکتوریل یک عدد، حاصل ضرب اعداد ۱ تا همان عدد است و تعریف ریاضی‌اش ذاتاً بازگشتی است: n! = n × (n-1)! و 0! = 1. ترجمه مستقیم این تعریف به پایتون:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

نکته تازه نسبت به مثال شمارش، این است که نتیجه فراخوانی درونی در محاسبه استفاده می‌شود. مسیر اجرای factorial(3) را تا ته دنبال کنید:

1. factorial(3) منتظر factorial(2) می‌ماند تا ضرب کند.
2. factorial(2) منتظر factorial(1) می‌ماند.
3. factorial(1) منتظر factorial(0) می‌ماند.
4. factorial(0) حالت پایه است: ۱ را برمی‌گرداند.
5. حالا ضرب‌ها از ته باز می‌شوند: ۱×۱، بعد ۲×۱، بعد ۳×۲ و جواب ۶.

پایتون این صف انتظارها را روی چیزی به نام پشته فراخوانی (Call Stack) نگه می‌دارد؛ هر فراخوانی معلق، یک خانه اشغال می‌کند و با بازگشت، خانه آزاد می‌شود.

مثال دوم؛ جمع ارقام

الگوی «مسئله کوچک‌تر + ترکیب نتیجه» را بار دوم ببینید. جمع ارقام یک عدد با % و // که در درس عملگرها یاد گرفتید:

def digit_sum(n):
    if n == 0:
        return 0
    return n % 10 + digit_sum(n // 10)

print(digit_sum(4931))

n % 10 رقم آخر را جدا می‌کند و n // 10 عدد را بدون آن رقم کوچک‌تر می‌کند؛ گام بازگشتی همین کوچک‌شدن است. جمع‌ها در مسیر بازگشت انجام می‌شوند: ۱+۳+۹+۴ برابر ۱۷.

مرز بازگشتی؛ وقتی پشته پر می‌شود

حالا عمداً قانون را بشکنید؛ تابعی بدون حالت پایه که خودش را با عدد بزرگ‌تر صدا می‌زند:

def boom(n):
    return boom(n + 1)

boom(1)

پایتون برای محافظت، عمق بازگشتی را محدود می‌کند؛ حد پیش‌فرض را می‌توانید ببینید:

import sys
print(sys.getrecursionlimit())

یعنی بیش از حدود هزار فراخوانی معلق ندارید. برای مسئله‌هایی با ورودی بزرگ، این محدودیت جدی است و راه‌حل معمولاً بازنویسی با حلقه است.

کی بازگشتی، کی حلقه؟

هر مسئله بازگشتی را می‌توان با حلقه هم حل کرد؛ جمع ارقام و فاکتوریل با for هم نوشته می‌شوند و برای این‌ها حلقه معمولاً ساده‌تر و سریع‌تر است. پس جای بازگشتی کجاست؟ جایی که مسئله ذاتاً شاخه‌ای است: پیمایش درخت پوشه‌های یک دیسک، تجزیه سند HTML یا JSON تودرتو، یا حل جدول‌های بازی. اینجا ساختار داده شاخه دارد و بازگشتی همان ساختار را در کد بازتاب می‌دهد؛ حلقه معادلش پیچیده و شکننده می‌شود.

تمرین‌ها

# Write your code here

def power(base, exp):
    if exp == 0:
        return 1
    return base * power(base, exp - 1)

print(power(2, 10))

::: :::

خلاصه

• بازگشتی یعنی تابعی که خودش را با مسئله‌ای کوچک‌تر صدا می‌زند.
• هر بازگشتی درست دو جزء دارد: حالت پایه متوقف‌کننده و گام بازگشتی نزدیک‌شونده.
• پشته فراخوانی فراخوانی‌های معلق را نگه می‌دارد و پایتون عمق آن را حدود هزار محدود می‌کند؛ بدون حالت پایه، RecursionError می‌گیرید.
• برای مسئله‌های خطی مثل فاکتوریل، حلقه معمولاً بهتر است؛ بازگشتی جای طبیعی‌اش ساختارهای شاخه‌ای است.
• طراحی بازگشتی با دو سؤال شروع می‌شود: کوچک‌ترین ورودی و ترکیب جواب کوچک‌تر.

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