بتل کد Battle Codeدارد باز می‌شود…

آموزش پایتون

تابع بازگشتی در پایتون: آموزش recursion با مثال ساده

۹ دقیقه مطالعه · ۳۰ مهر ۱۴۰۵

فهرست مطالب
  1. بازگشت یعنی چه؟ یک مثال از زندگی
  2. دو بخش هر تابع بازگشتی: حالت پایه و گام بازگشتی
  3. فاکتوریل: مثال کلاسیک بازگشت
  4. جمع عناصر لیست و لیست‌های تودرتو
  5. فیبوناچی: چرا نسخه‌ی ساده کند است؟
  6. عمق بازگشت و خطای RecursionError
  7. بازگشت یا حلقه؟ کدام بهتر است؟
  8. چطور یک تابع بازگشتی بنویسیم؟ قدم‌به‌قدم
  9. سؤال‌های پرتکرار

تابع بازگشتی (recursive function) تابعی است که خودش را صدا می‌زند تا یک مسئله‌ی بزرگ را با حل نسخه‌ی کوچک‌تری از همان مسئله حل کند. هر تابع بازگشتی دو بخش لازم دارد: حالت پایه (base case) که بدون صدا زدن دوباره جواب را برمی‌گرداند، و گام بازگشتی که تابع را با ورودی کوچک‌تر صدا می‌زند. بدون حالت پایه، تابع بی‌پایان خودش را صدا می‌زند تا پایتون با خطای RecursionError متوقفش کند.

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

بازگشت یعنی چه؟ یک مثال از زندگی

فرض کنید در صف طولانی سینما ایستاده‌اید و می‌خواهید بدانید نفر چندم هستید، اما سر صف را نمی‌بینید. از نفر جلویی می‌پرسید «تو نفر چندمی؟». او هم نمی‌داند و همین سؤال را از نفر جلویی‌اش می‌پرسد و این کار ادامه پیدا می‌کند تا به نفر اول صف برسد. نفر اول نیازی به پرسیدن ندارد؛ می‌داند که نفر اول است. این حالت پایه است. حالا جواب‌ها برمی‌گردند: هر کس عدد نفر جلویی را می‌گیرد، یکی به آن اضافه می‌کند و به نفر پشتی می‌گوید، تا جواب به شما برسد.

بازگشت دقیقاً همین است:

  • مسئله‌ی «من نفر چندمم؟» به مسئله‌ی کوچک‌تر «نفر جلویی چندم است؟» تبدیل می‌شود.
  • این کوچک شدن تا جایی ادامه پیدا می‌کند که جواب بدون پرسیدن معلوم باشد.
  • جواب‌ها به ترتیب برعکس برمی‌گردند و هر مرحله کار کوچکی رویشان انجام می‌دهد.

دو بخش هر تابع بازگشتی: حالت پایه و گام بازگشتی

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

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

countdown(3)
3
2
1
Go!

if n == 0 حالت پایه است: وقتی به صفر رسیدیم، Go! چاپ می‌شود و تابع دیگر خودش را صدا نمی‌زند. در غیر این صورت، تابع عدد را چاپ می‌کند و خودش را با n - 1 صدا می‌زند. چون هر فراخوانی عدد را یکی کم می‌کند، مطمئنیم بالاخره به صفر می‌رسیم. این دو شرط، یعنی وجود حالت پایه و نزدیک‌تر شدن به آن در هر فراخوانی، قلب هر تابع بازگشتی درست است.

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

فاکتوریل: مثال کلاسیک بازگشت

فاکتوریل یک عدد، حاصل‌ضرب همه‌ی عددهای ۱ تا خود آن عدد است. مثلاً فاکتوریل ۵ (که آن را 5! می‌نویسند) برابر است با ۵ × ۴ × ۳ × ۲ × ۱ = ۱۲۰. نکته‌ی جالب این است که 5! همان ۵ × 4! است؛ یعنی فاکتوریل هر عدد را می‌شود با فاکتوریل عدد کوچک‌تر حساب کرد. این یک تعریف بازگشتی است:

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

print(factorial(5))
print(factorial(10))
120
3628800

پشت صحنه: پشته‌ی فراخوانی

وقتی factorial(4) صدا زده می‌شود، نمی‌تواند فوراً جواب بدهد؛ باید منتظر factorial(3) بماند و آن هم منتظر factorial(2). پایتون همه‌ی این فراخوانی‌های نیمه‌تمام را روی پشته‌ی فراخوانی (call stack) نگه می‌دارد. با اضافه کردن چند print می‌شود این صف انتظار را دید:

def factorial(n, depth=0):
    pad = "  " * depth
    print(pad + f"factorial({n})")
    if n <= 1:
        result = 1
    else:
        result = n * factorial(n - 1, depth + 1)
    print(pad + f"-> {result}")
    return result

factorial(4)
factorial(4)
  factorial(3)
    factorial(2)
      factorial(1)
      -> 1
    -> 2
  -> 6
-> 24

فراخوانی‌ها به سمت پایین می‌روند تا به حالت پایه برسند و بعد جواب‌ها یکی‌یکی بالا می‌آیند:

فراخوانیچه حساب می‌کند؟جواب
factorial(4)4 * factorial(3)۲۴
factorial(3)3 * factorial(2)۶
factorial(2)2 * factorial(1)۲
factorial(1)حالت پایه۱

جمع عناصر لیست و لیست‌های تودرتو

جمع یک لیست

جمع یک لیست یعنی «عنصر اول + جمع بقیه‌ی لیست». جمع لیست خالی هم صفر است. همین دو جمله، تابع را می‌سازند:

def sum_list(nums):
    if not nums:
        return 0
    return nums[0] + sum_list(nums[1:])

print(sum_list([4, 7, 1, 9]))
print(sum_list([]))
21
0

nums[1:] لیستی است بدون عنصر اول، پس هر فراخوانی با لیستی یک خانه کوتاه‌تر کار می‌کند تا به لیست خالی برسد. با همین فکر می‌شود یک رشته را برعکس کرد:

def reverse(text):
    if len(text) <= 1:
        return text
    return reverse(text[1:]) + text[0]

print(reverse("python"))
nohtyp

لیست تودرتو: جایی که بازگشت می‌درخشد

حالا مسئله‌ای را ببینیم که با حلقه‌ی معمولی سخت است. کیسه‌ای داریم که داخلش عدد و کیسه‌های کوچک‌تر است و داخل آن‌ها هم ممکن است کیسه‌های دیگری باشد. نمی‌دانیم چند لایه دارد. جمع همه‌ی عددها چقدر است؟

def deep_sum(items):
    total = 0
    for item in items:
        if isinstance(item, list):
            total += deep_sum(item)
        else:
            total += item
    return total

bag = [1, [2, 3], [4, [5, [6]]]]
print(deep_sum(bag))
21

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

فیبوناچی: چرا نسخه‌ی ساده کند است؟

دنباله‌ی فیبوناچی این‌طور شروع می‌شود: ۰، ۱، ۱، ۲، ۳، ۵، ۸، ۱۳، … و هر عدد، جمع دو عدد قبلی است. تعریف بازگشتی‌اش خیلی ساده است، اما بیایید بشماریم تابع چند بار صدا زده می‌شود:

calls = 0

def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

for n in [10, 20, 25]:
    calls = 0
    print(f"fib({n}) = {fib(n)}, calls: {calls}")
fib(10) = 55, calls: 177
fib(20) = 6765, calls: 21891
fib(25) = 75025, calls: 242785

برای fib(25) تابع ۲۴۲٬۷۸۵ بار صدا زده شده است. این عدد برای fib(30) به ۲٬۶۹۲٬۵۳۷ و برای fib(40) به بیش از ۳۳۱ میلیون می‌رسد. دلیلش این است که هر فراخوانی دو فراخوانی دیگر می‌سازد و یک کار بارها و بارها تکرار می‌شود: fib(25) یک بار fib(23) را از راه fib(24) حساب می‌کند و یک بار دیگر مستقیم، و همین تکرار در همه‌ی سطح‌های پایین‌تر هم رخ می‌دهد.

راه حل: به خاطر سپردن جواب‌ها

راه حل این است که هر جوابی را که یک بار حساب کردیم، در یک دیکشنری نگه داریم و دفعه‌ی بعد از همان استفاده کنیم. به این روش مموایزیشن (memoization) یا به خاطر سپردن می‌گویند:

memo = {}

def fib(n):
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

print(fib(30))
print(fib(100))
832040
354224848179261915075

حالا fib(100) در یک چشم به هم زدن حساب می‌شود، چون هر عدد فقط یک بار محاسبه می‌شود. پایتون ابزار آماده‌ای هم برای همین کار دارد: اگر بالای تابع @lru_cache(maxsize=None) را از ماژول functools بنویسید، جواب‌ها خودکار ذخیره می‌شوند. البته فیبوناچی با یک حلقه‌ی ساده هم سریع حساب می‌شود:

def fib_loop(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_loop(10), fib_loop(100))
55 354224848179261915075

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

عمق بازگشت و خطای RecursionError

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

import sys

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

print(sys.getrecursionlimit())
try:
    forever(1)
except RecursionError as error:
    print("RecursionError:", error)
1000
RecursionError: maximum recursion depth exceeded

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

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

try:
    factorial(5000)
except RecursionError:
    print("too deep!")
print(len(str(factorial(500))))
too deep!
1135

factorial(500) بی‌دردسر حساب می‌شود و جوابش عددی ۱۱۳۵ رقمی است، اما factorial(5000) به ۵۰۰۰ فراخوانی تو در تو نیاز دارد و از سقف رد می‌شود. با sys.setrecursionlimit می‌شود این سقف را بالا برد، اما بالا بردن زیاد آن ممکن است برنامه را از کار بیندازد. راه درست برای ورودی‌های خیلی بزرگ، نوشتن نسخه‌ی حلقه‌ای است. سقف ۱۰۰۰ مقدار پیش‌فرض پایتون معمولی است و در محیط‌های دیگر ممکن است فرق کند.

بازگشت یا حلقه؟ کدام بهتر است؟

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

def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_loop(5), factorial_loop(10))
120 3628800

سؤال این نیست که کدام «درست» است؛ سؤال این است که کدام برای این مسئله روشن‌تر است:

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

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

چطور یک تابع بازگشتی بنویسیم؟ قدم‌به‌قدم

  1. کوچک‌ترین حالت را پیدا کنید. جوابش بدون هیچ محاسبه‌ی دیگری معلوم است: لیست خالی، عدد صفر یا رشته‌ی یک‌حرفی. این حالت پایه است و آن را اول تابع بنویسید.
  2. مسئله را به نسخه‌ی کوچک‌تر خودش ربط دهید. بپرسید: «اگر جواب مسئله‌ی کمی کوچک‌تر را داشتم، جواب این یکی را چطور می‌ساختم؟»
  3. به تابع اعتماد کنید. فرض کنید فراخوانی کوچک‌تر درست کار می‌کند و فقط مطمئن شوید قدم آخر را درست ساخته‌اید.
  4. مطمئن شوید به حالت پایه می‌رسید. هر فراخوانی باید ورودی را کوچک‌تر کند؛ n - 1، nums[1:] یا نصف لیست.
  5. با ورودی‌های کوچک امتحان کنید. با print یا با اجرای قدم‌به‌قدم ببینید فراخوانی‌ها چطور پیش می‌روند.

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

سؤال‌های پرتکرار

تابع بازگشتی در پایتون چیست؟

تابعی است که داخل بدنه‌ی خودش، خودش را صدا می‌زند. هر بار مسئله را کمی کوچک‌تر می‌کند تا به حالتی برسد که جوابش بدون محاسبه‌ی بیشتر معلوم است و بعد جواب‌ها را مرحله به مرحله کنار هم می‌گذارد.

حالت پایه چیست و اگر نباشد چه می‌شود؟

حالت پایه شرطی است که در آن تابع بدون صدا زدن دوباره‌ی خودش جواب را برمی‌گرداند؛ مثل if n == 0. اگر حالت پایه نباشد یا هیچ‌وقت به آن نرسیم، تابع بی‌پایان خودش را صدا می‌زند و پایتون با خطای RecursionError متوقفش می‌کند.

چرا فیبوناچی بازگشتی این‌قدر کند است؟

چون هر فراخوانی دو فراخوانی دیگر می‌سازد و جواب‌های یکسان بارها از نو حساب می‌شوند. مثلاً برای fib(25) تابع بیش از ۲۴۰ هزار بار صدا زده می‌شود. با ذخیره‌ی جواب‌ها در دیکشنری، استفاده از lru_cache یا نوشتن نسخه‌ی حلقه‌ای، این مشکل حل می‌شود.

حداکثر عمق بازگشت در پایتون چقدر است؟

در پایتون معمولی، سقف پیش‌فرض ۱۰۰۰ است و با sys.getrecursionlimit() می‌شود آن را دید. می‌شود با sys.setrecursionlimit سقف را بالا برد، اما برای ورودی‌های خیلی بزرگ، نسخه‌ی حلقه‌ای راه امن‌تری است.

بازگشت بهتر است یا حلقه؟

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

بازگشت در کجا به کار می‌رود؟

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

همین حالا روی Battle Code تمرین کن

مقاله‌های دیگر

همه‌ی مقاله‌ها