بازگشت پیشرفته

بازگشت به‌عنوان درخت

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

• عمق درخت = عمق بازگشت = حافظه پشته
• تعداد گره‌ها = تعداد کل فراخوانی‌ها = زمان
• پهنای هر گره = تعداد انتخاب‌ها در آن نقطه

مثال: درخت فیبوناچی

fib(4)
├── fib(3)
│   ├── fib(2)
│   │   ├── fib(1) ✓
│   │   └── fib(0) ✓
│   └── fib(1) ✓
└── fib(2)
    ├── fib(1) ✓
    └── fib(0) ✓

۹ گره برای fib(4)! رشد نمایی — و انگیزه memoization.

سه نوع الگوی بازگشت

بازگشت با انباشت (Accumulator)

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

# بازگشتی معمولی
def sum_rec(arr, i):
    if i == len(arr): return 0
    return arr[i] + sum_rec(arr, i + 1)

# با انباشت
def sum_acc(arr, i, acc=0):
    if i == len(arr): return acc
    return sum_acc(arr, i + 1, acc + arr[i])

تبدیل سیستماتیک به تکراری

1. پشته صریح بساز و ریشه را بگذار
2. تا خالی‌شدن پشته: گره بردار، پردازش کن، فرزندان را بگذار

هر الگوریتم بازگشتی این‌طور تبدیل می‌شود — DFS تکراری دقیقاً همین است!

جمع‌بندی

• بازگشت = درخت؛ عمق = حافظه، گره‌ها = زمان
• سه الگو: خطی، دوگانه، دسته‌ای
• انباشت: نتیجه در پارامتر — سریع‌تر
• تبدیل تکراری: پشته صریح — همیشه ممکن