# فصل ۰۲ — هزینهٔ `recursion`: درختِ فراخوانی و کاری که دوباره انجام می‌شود

<div dir="rtl">

# فصل ۰۲ — هزینهٔ `recursion`: درختِ فراخوانی و کاری که دوباره انجام می‌شود

## در این فصل چه یاد می‌گیری

فصلِ قبل تابعی داشت که در هر فراخوانی **یک بار** خودش را صدا می‌زد. این فصل تابعی می‌سازد که **دو بار** صدا می‌زند — و همان یک تفاوت کافی است تا یک ورودیِ کوچکِ ۲۴تایی **۱۵۰٬۰۴۹ فراخوانی** بخواهد.

بعد می‌فهمیم چرا: در آن درخت، **`fib(2)` دقیقاً ۲۸٬۶۵۷ بار حساب می‌شود**، هر بار از صفر. با یک `dict` جلوی این تکرار را می‌گیریم و همان ۱۵۰٬۰۴۹ به **۴۷** می‌رسد. در `n = 30` فاصله بازتر است: **۲٬۶۹۲٬۵۳۷ در برابرِ ۵۹.**

![درختی که هر شاخه‌اش به دو شاخه تقسیم می‌شود و برگ‌های یکسانِ بسیاری دارد](/lesson-assets/t4-s02-recursion-cost/prompt/01-image-call-tree.png)

آخر این فصل می‌توانی:

- درختِ فراخوانیِ یک `recursion` را بکشی و گره‌هایش را بشماری
- تشخیص بدهی کِی یک `recursion` دارد کارِ تکراری انجام می‌دهد
- با یک `dict` دستی، `memoisation` بنویسی و اثرش را با شمارش نشان بدهی
- بگویی چرا حتی نسخهٔ سریع هم یک هزینهٔ حافظه دارد که در جدولِ زمان دیده نمی‌شود

## قبل از شروع

**از فصلِ ۱:** حالتِ پایه، گامِ بازگشتی، `call stack` و پیامِ `RecursionError`.

**از ترمِ ۱ فصلِ ۵:** قاعدهٔ خواندنِ ستونِ نسبت — و مخصوصاً آخرین سطرش: **«بزرگ‌تر از `4` و رو به انفجار: نسبت خودش هم با `n` بزرگ می‌شود».** این فصل اولین جایی است که آن سطر را در یک کدِ واقعی می‌بینی.

</div>

| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیش‌فرضِ Colab) | کمتر از یک دقیقه |

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-4-recursion-sorting-searching/session-02-recursion-cost.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. یک تابع، و دو فراخوانی به‌جای یکی

دنبالهٔ فیبوناچی خودش را در تعریفِ خودش به‌کار می‌برد: هر عدد جمعِ دو عددِ قبلی است، و دو عددِ اول ۰ و ۱ هستند. این تعریف را مو به مو به کد تبدیل می‌کنیم.

</div>

```python
def fib(n):
    """تعریفِ خودِ دنباله، مو به مو."""
    if n < 2:                            # حالتِ پایه
        return n
    return fib(n - 1) + fib(n - 2)       # دو گامِ بازگشتی، نه یکی


def fib_traced(n, depth=0):
    """همان تابع، با چاپِ درختِ فراخوانی."""
    print("  " * depth + f"fib({n})")
    if n < 2:
        return n
    return fib_traced(n - 1, depth + 1) + fib_traced(n - 2, depth + 1)


print("fib(0..9):", [fib(k) for k in range(10)])
print()
fib_traced(5)
```

```text
fib(0..9): [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

fib(5)
  fib(4)
    fib(3)
      fib(2)
        fib(1)
        fib(0)
      fib(1)
    fib(2)
      fib(1)
      fib(0)
  fib(3)
    fib(2)
      fib(1)
      fib(0)
    fib(1)
```

<div dir="rtl">

**این شکل یک درخت است و اسمش هم همین است: درختِ فراخوانی.** هر گره یک فراخوانی است و فرزندانش فراخوانی‌هایی که خودش راه انداخته.

حالا با چشم بشمار: **`fib(3)` دو بار در این درخت هست و `fib(2)` سه بار.** هر کدامشان هم شاخه‌های خودشان را دوباره از صفر می‌سازند. **هیچ چیزی نگه داشته نمی‌شود، چون هیچ‌جا گفته نشده نگه داشته شود.**

## ۲. شمردنِ گره‌ها

> 🤔 **اول حدس بزن:** اگر `n` را دو برابر کنیم، تعدادِ فراخوانی چند برابر می‌شود؟ **یک عدد بنویس**، بعد جدول را ببین. (اگر گفتی «۲ یا ۴»، درست همان جایی هستی که این فصل می‌خواهد.)

</div>

```python
def fib_calls(n):
    """جواب، و تعدادِ فراخوانی‌ای که برای رسیدن به آن انجام شد."""
    calls = 0

    def go(k):
        nonlocal calls
        calls += 1
        if k < 2:
            return k
        return go(k - 1) + go(k - 2)

    return go(n), calls


print("fib(5) =", fib_calls(5)[0], "· فراخوانی:", fib_calls(5)[1])
table([(n, fib_calls(n)[1]) for n in (3, 6, 12, 24)], "فراخوانی", ",d")
```

```text
fib(5) = 5 · فراخوانی: 15
         n          فراخوانی     نسبت به سطر قبل
         3                 5                   —
         6                25                5.00
        12               465               18.60
        24           150,049              322.69
```

<div dir="rtl">

**`5.00`، بعد `18.60`، بعد `322.69`.** ستونِ نسبت به عددی نمی‌رسد که آن‌جا بماند؛ **خودش هم منفجر می‌شود.** این دقیقاً همان امضایی است که ترمِ ۱ فصلِ ۵ برای رشدِ نمایی نوشت، و تنها مرتبه‌ای است که این شکل را دارد.

نردبانِ ضربی این‌جا حرفش را زد، ولی نردبانِ **جمعی** چیزِ دیگری هم نشان می‌دهد:

</div>

```python
table([(n, fib_calls(n)[1]) for n in (20, 21, 22, 23, 24)], "فراخوانی", ",d")
```

```text
         n          فراخوانی     نسبت به سطر قبل
        20            21,891                   —
        21            35,421                1.62
        22            57,313                1.62
        23            92,735                1.62
        24           150,049                1.62
```

<div dir="rtl">

**هر بار که فقط **یکی** به `n` اضافه می‌شود، کار در `1.62` ضرب می‌شود** — و این عدد در هر چهار سطر یکی است. رشدِ نمایی همین است: **در هر قدم، ضرب در یک عددِ ثابت.** پایه‌اش این‌جا اتفاقاً `2` نیست، `1.62` است؛ ولی شکلِ رشد همان است و همان‌قدر هم بی‌رحم.

> 🌱 **ریشه‌اش کجاست:** چرا ضرب شدنِ پیاپی در یک عددِ کوچک این‌قدر زود از کنترل خارج می‌شود — و چرا شهودِ آدم تقریباً همیشه کم‌برآوردش می‌کند — در [ریشه ترمِ ۴ فصل ۷](/courses/risheh/lessons/term-4-functions/session-07-exponential) با مثالِ ملموس ساخته شده. **نکتهٔ کلیدی همان‌جاست: در رشدِ نمایی، بزرگیِ ضریب مهم نیست؛ ثابت بودنش مهم است.**

## ۳. چرا: همان کار، بارها

عدد `150,049` از جایی نیامده. آن را می‌شود شکافت.

</div>

```python
from collections import Counter


def fib_who(n):
    """چند بار هر fib(k) صدا زده می‌شود."""
    seen = Counter()

    def go(k):
        seen[k] += 1
        if k < 2:
            return k
        return go(k - 1) + go(k - 2)

    go(n)
    return seen


counts = fib_who(24)
print("در fib(24):")
for k in (24, 23, 22, 20, 15, 10, 5, 2):
    print(f"  fib({k:>2}) صدا زده شد: {counts[k]:>6,} بار")
```

```text
در fib(24):
  fib(24) صدا زده شد:      1 بار
  fib(23) صدا زده شد:      1 بار
  fib(22) صدا زده شد:      2 بار
  fib(20) صدا زده شد:      5 بار
  fib(15) صدا زده شد:     55 بار
  fib(10) صدا زده شد:    610 بار
  fib( 5) صدا زده شد:  6,765 بار
  fib( 2) صدا زده شد: 28,657 بار
```

<div dir="rtl">

**`fib(2)` جوابش همیشه `1` است و ۲۸٬۶۵۷ بار از صفر حساب می‌شود.**

**منشأِ انفجار همین است، نه خودِ `recursion`.** تابعِ فصلِ ۱ هم `recursion` داشت و خطی درآمد، چون هر فراخوانی مسئلهٔ **تازه‌ای** حل می‌کرد. این‌جا شاخهٔ چپ و شاخهٔ راست بخشِ بزرگی از کارشان مشترک است و هیچ‌کدام از دیگری خبر ندارد.

## ۴. `memoisation`: هر جواب فقط یک بار

راهِ حل به اندازهٔ مسئله ساده است: **هر جوابی که حساب شد، در یک `dict` نگه دار؛ قبل از حساب کردن، اول آن‌جا را نگاه کن.** اسمِ این کار `memoisation` است و کلِ ابزارش یک `dict` است.

> 💡 **نکته:** پایتون ابزارِ آماده‌ای هم دارد که همین کار را خودکار می‌کند. **این دوره عمداً سراغش نمی‌رود** و آن را دستی می‌نویسد، چون درسِ این فصل خودِ `dict` و خودِ شمارش است، نه یک تزئینِ آماده. آن ابزار موضوعِ دورهٔ داربست است.

</div>

```python
sys.setrecursionlimit(6_000)             # همان احتیاطِ فصلِ ۱


def fib_memo(n, memo=None):
    """همان تعریف، فقط جوابِ هر k یک بار حساب و در dict نگه داشته می‌شود."""
    if memo is None:
        memo = {}
    if n in memo:                        # قبلاً حسابش کرده‌ایم
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]


def fib_memo_calls(n):
    """تعدادِ فراخوانیِ نسخهٔ memo، و بیشترین عمقی که به آن رسید."""
    calls = 0
    deepest = 0

    def go(k, memo, depth):
        nonlocal calls, deepest
        calls += 1
        deepest = max(deepest, depth)
        if k in memo:
            return memo[k]
        if k < 2:
            return k
        memo[k] = go(k - 1, memo, depth + 1) + go(k - 2, memo, depth + 1)
        return memo[k]

    return go(n, {}, 1), calls, deepest


print("جوابِ دو نسخه یکی است؟", fib(24) == fib_memo(24))
print("در n = 24  ·  با memo:", fib_memo_calls(24)[1],
      "· بدونِ memo:", f"{fib_calls(24)[1]:,}")
print("در n = 30  ·  با memo:", fib_memo_calls(30)[1],
      "· بدونِ memo:", f"{fib_calls(30)[1]:,}")
```

```text
جوابِ دو نسخه یکی است؟ True
در n = 24  ·  با memo: 47 · بدونِ memo: 150,049
در n = 30  ·  با memo: 59 · بدونِ memo: 2,692,537
```

<div dir="rtl">

**۵۹ در برابرِ ۲٬۶۹۲٬۵۳۷ — بیش از چهل‌وپنج هزار برابر کمتر، با جوابِ کاملاً یکسان.** و به سطرِ اول دقت کن: تفاوت با بزرگ‌تر شدنِ `n` بازتر می‌شود، چون یکی خطی است و دیگری نمایی.

> 🤔 **اول حدس بزن:** ستونِ نسبتِ تعدادِ فراخوانیِ نسخهٔ `memo` چه عددی می‌دهد؟ **بنویسش**، بعد جدول را ببین.

</div>

```python
MEMO = [100, 200, 400, 800]
table([(n, fib_memo_calls(n)[1]) for n in MEMO], "فراخوانی", ",d")
```

```text
         n          فراخوانی     نسبت به سطر قبل
       100               199                   —
       200               399                2.01
       400               799                2.00
       800             1,599                2.00
```

<div dir="rtl">

**`2.00` — یعنی `O(n)`.** از نمایی به خطی، فقط با یک `dict`. **و منطقش را می‌شود در یک جمله نوشت: هر `k` بینِ ۰ و `n` دقیقاً یک بار واقعاً حساب می‌شود؛ بقیهٔ فراخوانی‌ها فقط از `dict` می‌خوانند.**

## ۵. هزینه‌ای که در جدولِ فراخوانی دیده نمی‌شود

نسخهٔ `memo` رایگان نیست. دو چیز نگه می‌دارد: خودِ `dict`، و **عمقِ `call stack`**.

</div>

```python
table([(n, fib_memo_calls(n)[2]) for n in MEMO], "بیشترین عمق", ",d")
```

```text
         n       بیشترین عمق     نسبت به سطر قبل
       100               100                   —
       200               200                2.00
       400               400                2.00
       800               800                2.00
```

<div dir="rtl">

**عمق دقیقاً برابرِ `n` است و ستونِ نسبتش `2.00`.** یعنی حافظه‌ای که این تابع مصرف می‌کند با `n` خطی بالا می‌رود — و برخلافِ زمان، **این هزینه سقفِ سخت دارد**، چون `call stack` سقف دارد.

</div>

```python
def fib_loop(n):
    """همان دنباله، بدونِ هیچ فراخوانی و بدونِ هیچ عمقی."""
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


print("سه نسخه یک جواب می‌دهند؟", fib(24) == fib_memo(24) == fib_loop(24))
print("تعدادِ رقم‌های fib(10,000):", len(str(fib_loop(10_000))))
try:
    fib_memo(10_000)
except RecursionError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
سه نسخه یک جواب می‌دهند؟ True
تعدادِ رقم‌های fib(10,000): 2090
RecursionError: maximum recursion depth exceeded
```

<div dir="rtl">

**حلقه `fib(10,000)` را می‌دهد — عددی با ۲٬۰۹۰ رقم — و نسخهٔ `memo` روی همان ورودی می‌شکند.** نه چون کند است؛ چون **عمیق** است. `memoisation` مرتبهٔ **زمان** را درست کرد و به مرتبهٔ **حافظه** دست نزد.

> ✅ **چک کن:** `MEMO` را به `[50, 100, 200, 400]` ببر و هر دو جدولِ این بخش را دوباره بگیر. **ستونِ نسبتِ عمق باید دقیقاً `2.00` بماند و ستونِ نسبتِ فراخوانی `2.01` یا `2.00` — چون تعدادِ فراخوانی `2n - 1` است و آن «منهای یک» در اندازه‌های کوچک‌تر خودش را در رقمِ دوم نشان می‌دهد. سطرِ اولِ جدولِ عمق باید `50` شود.** اگر عمق ثابت ماند، احتمالاً `depth + 1` را جایی `depth` نوشته‌ای و شمارنده اصلاً بالا نمی‌رود.

## ۶. دو اشتباهی که در نوشتنِ `memo` پیش می‌آید

</div>

```python
def count_no_put(n):
    """اشتباهِ اول: از memo می‌خواند ولی هیچ‌وقت چیزی در آن نمی‌گذارد."""
    calls = 0

    def go(k, memo):
        nonlocal calls
        calls += 1
        if k in memo:
            return memo[k]
        if k < 2:
            return k
        return go(k - 1, memo) + go(k - 2, memo)

    return go(n, {}), calls


answer, calls = count_no_put(24)
print("جوابش درست است؟", answer == fib(24))
print("فراخوانی با این «memo» :", f"{calls:,}")
print("فراخوانی بدونِ memo اصلاً:", f"{fib_calls(24)[1]:,}")


def fib_memo_broken(n, memo):
    """اشتباهِ دوم: بدونِ «اگر هست» مستقیم از memo می‌خواند."""
    if n < 2:
        return n
    return memo[n - 1] + memo[n - 2]


try:
    fib_memo_broken(10, {})
except KeyError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
جوابش درست است؟ True
فراخوانی با این «memo» : 150,049
فراخوانی بدونِ memo اصلاً: 150,049
KeyError: 9
```

<div dir="rtl">

> 🔧 **اگر کار نکرد:** **اشتباهِ اول هیچ پیامی ندارد و بدترینشان است.** کد `if k in memo` را دارد، جوابِ درست می‌دهد، و **دقیقاً همان ۱۵۰٬۰۴۹ فراخوانیِ نسخهٔ بدونِ `memo` را انجام می‌دهد** — چون `memo` هیچ‌وقت پر نمی‌شود. تنها راهِ گرفتنش همین است: **شمارنده بگذار.** اگر شمارنده نداشتی، فقط می‌گفتی «سریع نشد» و دنبالِ دلیلِ اشتباه می‌گشتی.
>
> اشتباهِ دوم صریح است: `KeyError: 9` یعنی سراغِ کلیدِ `9` رفته‌ای و آن‌جا نبوده. **`memo` یک `cache` است، نه یک جدولِ آماده** — قبل از خواندن باید یا مطمئن شوی هست، یا با `.get` جوابِ نبودنش را هم پیش‌بینی کنی.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** سه نسخه از یک تابعِ واحد — `recursion` ساده، `recursion` با `memo`، و حلقه — با جوابِ تأییدشدهٔ برابر. **در کدام بازهٔ `n`؟** ۳ تا ۳۰ برای نسخهٔ بدونِ `memo` (بالاتر از آن در چند دقیقه هم تمام نمی‌شود) و ۱۰۰ تا ۸۰۰ برای نسخهٔ `memo`، که سقفش را عمقِ `call stack` تعیین کرده. **با چند تکرار، و کمینه یا میانگین؟** یک اجرا برای همه؛ **هر عددِ این فصل یک شمارش است، نه یک زمان** — و شمارش قطعی است.

> 🤖 **از دستیارت بپرس:** «چرا `recursion` فیبوناچی این‌قدر گران است ولی `recursion` جمعِ یک `list` نه؟» بعد این را هم بپرس: **«اگر `memo` را به تابع بدهم ولی هیچ‌وقت چیزی در آن نگذارم، چه اتفاقی می‌افتد؟»** — جوابِ درست باید بگوید کد کار می‌کند و هیچ چیزی سریع نمی‌شود. اگر دستیارت گفت «خطا می‌دهد»، **خروجیِ بخشِ ۶ را جلویش بگذار.**

## واژه‌های تازهٔ این فصل

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| call tree | کال‌تری | درختِ همهٔ فراخوانی‌هایی که یک فراخوانی راه می‌اندازد |
| `memoisation` | مموایزیشن | نگه داشتنِ جوابِ هر ورودی تا دوباره حساب نشود |
| overlapping subproblems | اورلپینگ ساب‌پرابلمز | زیرمسئله‌هایی که بارها در درختِ فراخوانی تکرار می‌شوند |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: منشأِ رشدِ نمایی در `fib` خودِ `recursion` بود یا چیزِ دیگری؟

**تمرینِ اجباری:** با `recursion` تابعی بنویس که تعدادِ راه‌های بالا رفتن از `n` پله را حساب کند، وقتی در هر قدم می‌شود یک یا دو پله برداشت. **اول جدولِ فراخوانیِ نسخهٔ ساده را بگیر** و بگو ستونِ نسبت چه عددی می‌دهد. بعد نسخهٔ `memo`دارش را بنویس و جدولش را هم بگیر. **سؤالِ اصلی: چرا این مسئله و فیبوناچی درختِ فراخوانیِ یکسانی دارند؟** جوابت باید به تعریفِ هر دو برگردد، نه به عددهایشان.

**تمرینِ ستاره‌دار ⭐:** نسخهٔ `memo` را طوری بنویس که `dict` بینِ فراخوانی‌های مختلفِ خودِ تابع هم زنده بماند (یعنی `fib_memo(30)` بعد از `fib_memo(29)` تقریباً هیچ کاری نکند). **قبل از اجرا پیش‌بینی کن** فراخوانیِ دوم چند فراخوانی می‌خورد، بعد اجرا کن و **خطای پیش‌بینی‌ات را بنویس**. حالا سؤالِ سخت: **این `dict` کِی باید خالی شود؟** جوابت باید یک هزینه را نام ببرد که تا حالا در این فصل اندازه نگرفته‌ایم.

## در فصل بعد

دو فصل شد که دربارهٔ خودِ `recursion` حرف زدیم. از فصلِ بعد سراغِ کاری می‌رویم که `recursion` در آن واقعاً برنده است — ولی اول باید ببینیم بدونش چه شکلی است.

فصلِ بعد **دو مرتب‌سازی را با دست انجام می‌دهد** و مقایسه‌هایشان را می‌شمارد. هر دو `O(n²)` هستند: در `n = 2,000` یکی `1,999,000` مقایسه می‌کند و دیگری `1,022,176`. **ولی وقتی ورودی از پیش مرتب باشد، دومی به `1,999` می‌افتد و ستونِ نسبتش `2.00` می‌شود** — و اولی هنوز همان `1,999,000` است.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t4/s02-recursion-cost (یادستان, Yaadestan)
