بازگشت (Recursion)

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

بازگشت چیست؟

بازگشت (Recursion) یعنی تابعی که برای حل مسئله، خودش را با ورودی کوچک‌تر صدا می‌زند. مثل دو آینه روبه‌رو که تصویر در تصویر می‌سازند — اما با یک توقف!

دو جزء الزامی هر تابع بازگشتی

  1. حالت پایه (Base Case): کوچک‌ترین مسئله که مستقیم حل می‌شود — بدون این، حلقه بی‌نهایت!
  2. مرحله بازگشتی (Recursive Case): مسئله را به زیرمسئله کوچک‌تر بشکن و به خودت واگذار کن
def factorial(n):
    if n <= 1:
        return 1           # حالت پایه
    return n * factorial(n - 1)  # مرحله بازگشتی

چطور کار می‌کند؟ پشته فراخوانی

factorial(4)
= 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * 2 * factorial(1)
= 4 * 3 * 2 * 1        ← حالت پایه!
= 24

هر فراخوانی روی پشته فراخوانی (Call Stack) می‌نشیند تا حالت پایه برسد؛ بعد جواب‌ها به ترتیب برمی‌گردند و ترکیب می‌شوند.

مثال کلاسیک: فیبوناچی

fib(n) = fib(n-1) + fib(n-2)
fib(0) = 0, fib(1) = 1   ← حالت‌های پایه

اما نسخه ساده آن محاسبات تکراری دارد (fib(4) چندبار!) — راه‌حل: memoization در مبحث برنامه‌نویسی پویا.

بازگشت در ساختارهای داده

بازگشت با ساختارهای خودمتشابه طبیعی جور است:

خطر: سرریز پشته

هر فراخوانی حافظه پشته مصرف می‌کند؛ عمق زیاد (مثل factorial(100000)) = Stack Overflow! راه‌حل‌ها:

بازگشت یا تکرار؟

معیاربازگشتیتکراری
خوانایی (مسائل بازگشتی)✓ عالیپیچیده
حافظهO(عمق) پشتهO(1) ✓
خطر سرریزدارد ✗ندارد ✓
ساختارهای تودرتو✓ طبیعینیاز به پشته دستی
نکته: هر الگوریتم بازگشتی قابل تبدیل به تکراری است (با پشته صریح) و برعکس. انتخاب به خوانایی و محدودیت‌ها بستگی دارد.

جمع‌بندی

این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.

ابزارهای مرتبط