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

<div dir="rtl">

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

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

تا این‌جای دوره هر کاری با حلقه انجام شده. این فصل ابزارِ دومی می‌آورد که بعضی مسئله‌ها با آن **کوتاه‌تر و روشن‌تر** نوشته می‌شوند: تابعی که خودش را صدا می‌زند.

و بلافاصله هزینه‌اش را هم می‌شماریم. **جمعِ یک `list` با ۴٬۰۰۰ عضو، ۴٬۰۰۱ فراخوانی می‌خواهد و ستونِ نسبتش `2.00` است.** ولی اگر همان تابع را با برش بنویسی — که طبیعی‌ترین شکلِ نوشتنش هم هست — **۷٬۹۹۸٬۰۰۰ عضو کپی می‌شود و ستونِ نسبت `4.00`.** و روی یک `list` با ۲۰۰٬۰۰۰ عضو، `recursion` اصلاً اجرا نمی‌شود: پایتون با یک پیامِ مشخص جلویش را می‌گیرد.

![جعبه‌های تودرتو که هرکدام نسخهٔ کوچک‌ترِ خودش را در بر دارد و درونی‌ترینشان توپر است](/lesson-assets/t4-s01-recursion/prompt/01-image-nested-boxes.png)

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

- تابعی بنویسی که خودش را صدا می‌زند، با **حالتِ پایه** و **گامِ بازگشتی**
- بگویی `call stack` چیست و چرا عمقش یک منبعِ محدود است
- `RecursionError` را بخوانی و بفهمی چه چیزی را گزارش می‌کند
- هر `recursion` را به یک حلقه برگردانی و برابریِ جواب را ثابت کنی

## قبل از شروع

**از ترمِ ۲ فصلِ ۷:** انضباطِ `LIFO` — آخرین چیزی که گذاشتی، اولین چیزی است که برمی‌داری. **آن فصل `stack` را با `list` ساخت؛ این فصل نشان می‌دهد پایتون خودش یکی دارد.**

**از ترمِ ۲ فصلِ ۵:** قاعدهٔ تشخیصِ `O(n²)` — یک عملِ `O(n)` داخلِ حلقه‌ای که `n` بار می‌چرخد. بخشِ ۳ همان قاعده را در جایی پیدا می‌کند که اصلاً حلقه‌ای در کار نیست.

</div>

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

<div dir="rtl">

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

## ۱. کوچک‌ترین نسخهٔ ممکن، با دست

جمعِ یک `list` را می‌شود این‌طور تعریف کرد: **جمعِ کلِ فهرست یعنی عضوِ اول، به‌علاوهٔ جمعِ بقیه‌اش.** این تعریف به خودش ارجاع می‌دهد و همان‌طور که هست به کد تبدیل می‌شود — به شرطی که بگوییم کِی باید بایستد.

</div>

```python
def sum_traced(values, depth=0):
    """جمعِ یک list که خودش را روی دنبالهٔ کوتاه‌ترِ بعدی صدا می‌زند."""
    pad = "  " * depth
    print(f"{pad}sum_traced({values})")
    if not values:                       # حالتِ پایه
        print(f"{pad}-> 0   (حالتِ پایه)")
        return 0
    answer = values[0] + sum_traced(values[1:], depth + 1)
    print(f"{pad}-> {values[0]} + {answer - values[0]} = {answer}")
    return answer


print("جواب:", sum_traced([4, 8, 15, 16]))
```

```text
sum_traced([4, 8, 15, 16])
  sum_traced([8, 15, 16])
    sum_traced([15, 16])
      sum_traced([16])
        sum_traced([])
        -> 0   (حالتِ پایه)
      -> 16 + 0 = 16
    -> 15 + 16 = 31
  -> 8 + 31 = 39
-> 4 + 39 = 43
جواب: 43
```

<div dir="rtl">

**به شکلِ خروجی نگاه کن: اول همه‌چیز تو می‌رود، بعد همه‌چیز برمی‌گردد.** پنج فراخوانی رفتند تا ته، و بعد جواب‌ها یکی‌یکی به بالا پس داده شدند.

هر تابعی که خودش را صدا می‌زند دقیقاً دو تکه دارد و **هیچ‌کدامشان اختیاری نیست**:

- **حالتِ پایه** — کوچک‌ترین حالتی که جوابش را بدونِ صدا زدنِ خودمان می‌دانیم. این‌جا: فهرستِ خالی، جمع صفر.
- **گامِ بازگشتی** — مسئله را به یک مسئلهٔ **کوچک‌تر از همان جنس** تبدیل می‌کند. این‌جا: یک عضو کمتر.

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

## ۲. حالتِ پایه را بردار

</div>

```python
def sum_no_base(values):
    """همان تابع، فقط حالتِ پایه‌اش برداشته شده."""
    return values[0] + sum_no_base(values[1:])


def countdown(n):
    """این یکی به فهرستِ خالی هم نمی‌رسد — هیچ‌وقت."""
    return countdown(n - 1)


try:
    sum_no_base([4, 8, 15, 16])
except IndexError as err:
    print(f"{type(err).__name__}: {err}")

try:
    countdown(4)
except RecursionError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
IndexError: list index out of range
RecursionError: maximum recursion depth exceeded
```

<div dir="rtl">

> 🔧 **اگر کار نکرد:** **دو تابعِ معیوب، دو پیامِ کاملاً متفاوت.** `sum_no_base` به فهرستِ خالی می‌رسد و چون کسی نگفته آن‌جا بایستد، `values[0]` را روی چیزی صدا می‌زند که عضوی ندارد: `IndexError`. **این خطا دربارهٔ `recursion` هیچ چیزی نمی‌گوید و همین گمراه‌کننده است** — دنبالِ اشکالِ اندیس می‌گردی، در حالی که اشکال نبودِ حالتِ پایه است.
>
> `countdown` هیچ‌وقت به هیچ مرزی نمی‌رسد و پایتون خودش جلویش را می‌گیرد: `RecursionError: maximum recursion depth exceeded`. **این پیام تقریباً همیشه یک معنی دارد: یا حالتِ پایه نداری، یا گامِ بازگشتی‌ات به آن نزدیک نمی‌شود.** اولین کاری که باید بکنی این است که بپرسی «چه چیزی در هر فراخوانی کوچک‌تر می‌شود؟» — اگر جوابی نداشتی، پیدایش کرده‌ای.

## ۳. `call stack`: همان `LIFO`، این بار مالِ پایتون

چرا پایتون سقف دارد؟ چون هر فراخوانی که تمام نشده باید **یادش بماند**: کدام تابع بود، متغیرهایش چه بودند، و بعد از برگشتن باید کجا ادامه بدهد. این یادداشت‌ها روی هم انباشته می‌شوند و **دقیقاً همان انضباطِ `LIFO`ی ترمِ ۲ فصلِ ۷ را دارند**: آخرین فراخوانی اولین چیزی است که تمام می‌شود. اسمِ این انباشته `call stack` است.

</div>

```python
def deepest():
    """تا جایی که پایتون اجازه بدهد پایین می‌رود و عمقِ رسیده را برمی‌گرداند."""
    def down(depth):
        try:
            return down(depth + 1)
        except RecursionError:
            return depth
    return down(1)


print("سقفِ اعلام‌شدهٔ پایتون:", sys.getrecursionlimit())
print("عمقی که واقعاً رسیدیم :", deepest())
```

```text-approx
سقفِ اعلام‌شدهٔ پایتون: 1000
عمقی که واقعاً رسیدیم : 998
```

<div dir="rtl">

**عددِ دوم همیشه کمی کمتر از اولی است**، چون وقتی `deepest` صدا زده می‌شود چند فراخوانی از قبل روی `call stack` نشسته‌اند و سهمشان را برداشته‌اند. عددِ تو ممکن است یکی‌دو تا فرق کند؛ **چیزی که فرق نمی‌کند وجودِ سقف است.**

> ⚠️ **مواظب باش:** `sys.setrecursionlimit` این سقف را بالا می‌برد و **کارِ بی‌خطری نیست.** سقفْ محافظِ توست: با عددِ خیلی بزرگ، به‌جای یک استثنای تمیز، **کلِ نشستِ Colab بدونِ هیچ پیامی می‌میرد** و هر چه در حافظه داشتی از دست می‌رود. هر جای این ترم که لازمش داریم، عددِ محافظه‌کارانه می‌گذاریم و می‌گوییم چرا.

## ۴. یک `O(n²)` که هیچ حلقه‌ای ندارد

نسخهٔ بخشِ ۱ یک اشکالِ پنهان دارد. `values[1:]` **یک `list` تازه می‌سازد و همه‌چیز را در آن کپی می‌کند** — و این کار در هر فراخوانی تکرار می‌شود. نسخهٔ دوم به‌جای برش، یک اندیس جلو می‌برد.

**یک کلمهٔ تازه در کدِ بعدی هست که باید قبلش گفته شود: `nonlocal`.** یک تابعِ درونی، متغیرهای تابعِ بیرونی را **می‌خواند** بدونِ هیچ اعلامی؛ ولی اگر بخواهد **بنویسدشان**، پایتون به‌جای نوشتن یک متغیرِ تازهٔ محلی می‌سازد و بیرونی دست‌نخورده می‌ماند. **`nonlocal copied` دقیقاً یک جمله می‌گوید: «این همان `copied`ِ بیرونی است، می‌خواهم خودش را عوض کنم.»** از این‌جا به بعدِ ترم، هر شمارنده‌ای که داخلِ یک تابعِ تودرتو بالا می‌رود همین یک خط را لازم دارد.

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

</div>

```python
sys.setrecursionlimit(6_000)             # با احتیاط، و فقط تا همین حد


def sum_slice(values):
    """نسخهٔ برشی: هر فراخوانی یک list تازه می‌سازد."""
    if not values:
        return 0
    return values[0] + sum_slice(values[1:])


def sum_index(values, i=0):
    """نسخهٔ اندیسی: هیچ list تازه‌ای ساخته نمی‌شود."""
    if i == len(values):
        return 0
    return values[i] + sum_index(values, i + 1)


LADDER = [500, 1_000, 2_000, 4_000]
data = {n: list(range(n)) for n in LADDER}
print("جوابِ دو نسخه یکی است؟",
      sum_slice(data[500]) == sum_index(data[500]) == sum(data[500]))
```

```text
جوابِ دو نسخه یکی است؟ True
```

```python
def copied_by_slice(values):
    """تعدادِ عضوی که نسخهٔ برشی واقعاً کپی می‌کند — شمرده، نه حساب‌شده."""
    copied = 0

    def walk(vals):
        nonlocal copied
        if not vals:
            return 0
        rest = vals[1:]
        copied += len(rest)
        return vals[0] + walk(rest)

    walk(values)
    return copied


table([(n, copied_by_slice(data[n])) for n in LADDER], "عضوِ کپی‌شده", ",d")
```

```text
         n      عضوِ کپی‌شده     نسبت به سطر قبل
       500           124,750                   —
     1,000           499,500                4.00
     2,000         1,999,000                4.00
     4,000         7,998,000                4.00
```

<div dir="rtl">

**`4.00` — یعنی `O(n²)`، در تابعی که یک خط حلقه هم ندارد.**

قاعدهٔ ترمِ ۲ فصلِ ۵ می‌گفت «یک عملِ `O(n)` داخلِ حلقهٔ `n`تایی». این‌جا حلقه‌ای نیست، ولی **`recursion` خودش همان حلقه است**: `n` فراخوانی، و در هر کدام یک برشِ `O(n)`. **قاعده هیچ تغییری نکرده، فقط حلقه اسمِ دیگری دارد.**

حالا همان کار، با اندیس به‌جای برش:

</div>

```python
def call_count(values):
    """تعدادِ فراخوانیِ نسخهٔ اندیسی."""
    calls = 0

    def walk(i):
        nonlocal calls
        calls += 1
        if i == len(values):
            return 0
        return values[i] + walk(i + 1)

    walk(0)
    return calls


table([(n, call_count(data[n])) for n in LADDER], "فراخوانی", ",d")
```

```text
         n          فراخوانی     نسبت به سطر قبل
       500               501                   —
     1,000             1,001                2.00
     2,000             2,001                2.00
     4,000             4,001                2.00
```

<div dir="rtl">

**`2.00` — یعنی `O(n)`، با همان جواب.** یک تفاوتِ کوچک در نحوهٔ نوشتن، دو مرتبهٔ متفاوت.

> ✅ **چک کن:** `LADDER` را به `[250, 500, 1_000, 2_000]` ببر و **فقط** جدولِ کپی را دوباره بگیر. سطرِ اول باید `31,125` بدهد و ستونِ نسبت باید هنوز `4.00` بماند. **اگر نسبت `2.00` شد، احتمالاً `copied += len(rest)` را به `copied += 1` تبدیل کرده‌ای** — و آن‌وقت داری فراخوانی‌ها را می‌شماری، نه کپی‌ها.

## ۵. هر `recursion` را می‌شود به حلقه برگرداند

</div>

```python
def sum_loop(values):
    """همان کار، بدونِ هیچ فراخوانی‌ای."""
    running = 0
    for v in values:
        running += v
    return running


print("جوابِ حلقه با جوابِ recursion یکی است؟",
      sum_loop(data[4_000]) == sum_index(data[4_000]))
print("\n— recursion با اندیس")
table([(n, 1000 * clock(lambda v=data[n]: sum_index(v), repeat=3)) for n in LADDER],
      "زمان (ms)", ",.3f")
print("\n— حلقه")
table([(n, 1000 * clock(lambda v=data[n]: sum_loop(v), repeat=3)) for n in LADDER],
      "زمان (ms)", ",.3f")

same = data[4_000]
rec = clock(lambda: sum_index(same), repeat=3)
loop = clock(lambda: sum_loop(same), repeat=3)
print(f"\nn = 4,000  ·  recursion: {1000 * rec:.3f} ms"
      f"  ·  حلقه: {1000 * loop:.3f} ms  ·  نسبت: {rec / loop:.1f}")
```

```text-approx
جوابِ حلقه با جوابِ recursion یکی است؟ True

— recursion با اندیس
         n         زمان (ms)     نسبت به سطر قبل
       500             0.071                   —
     1,000             0.149                2.11
     2,000             0.311                2.09
     4,000             0.654                2.10

— حلقه
         n         زمان (ms)     نسبت به سطر قبل
       500             0.010                   —
     1,000             0.021                2.00
     2,000             0.041                2.00
     4,000             0.085                2.04

n = 4,000  ·  recursion: 0.662 ms  ·  حلقه: 0.085 ms  ·  نسبت: 7.8
```

<div dir="rtl">

**هر دو نسبتِ `2` می‌دهند — مرتبه‌شان یکی است.** ولی روی این ماشین `recursion` نزدیک به **هشت برابر** کندتر درآمد. عددهای تو فرق می‌کنند؛ **این نسبت نباید فرق کند**، چون دلیلش ساختاری است: هر فراخوانی یک قابِ تازه روی `call stack` می‌سازد و جمع کردنِ دو عدد در مقایسه با آن تقریباً رایگان است. **این همان ثابتِ پنهانِ ترمِ ۱ فصلِ ۹ است**، این بار به‌شکلِ هزینهٔ فراخوانی.

و یک تفاوتِ سخت‌تر هم هست:

</div>

```python
big = list(range(200_000))
print("حلقه روی ۲۰۰٬۰۰۰ عضو:", sum_loop(big))
try:
    sum_index(big)
except RecursionError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
حلقه روی ۲۰۰٬۰۰۰ عضو: 19999900000
RecursionError: maximum recursion depth exceeded
```

<div dir="rtl">

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

**پس `recursion` اصلاً برای چه خوب است؟** برای مسئله‌هایی که تعریفِ خودشان `recursion` دارد و عمقشان **`log n`** است، نه `n`. فصل‌های ۴ و ۵ دو تای مهم‌ترینشان را می‌سازند و آن‌جا عمق در حدِ چند ده می‌ماند، نه چند هزار.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** سه نسخه از یک کارِ واحد — `recursion` با برش، `recursion` با اندیس، و حلقه — با ورودیِ کاملاً یکسان و جوابِ تأییدشدهٔ برابر. **در کدام بازهٔ `n`؟** ۵۰۰ تا ۴٬۰۰۰، که سقفش را عمقِ `call stack` تعیین کرده نه صبرِ ما. **با چند تکرار، و کمینه یا میانگین؟** جدولِ کپی و جدولِ فراخوانی یک اجرا، چون شمارش‌اند و قطعی؛ جدولِ زمان سه تکرار به‌علاوهٔ گرم‌کننده، کمینه.

> 🤖 **از دستیارت بپرس:** «تفاوتِ حالتِ پایه و گامِ بازگشتی را با یک مثال بگو.» بعد این را هم بپرس: **«چرا `sum_slice` مرتبه‌اش `O(n²)` است ولی `sum_index` نه؟»** — جوابِ درست باید به کپیِ برش برسد، نه به تعدادِ فراخوانی. اگر دستیارت گفت «هر دو `O(n)` هستند»، **جدولِ بخشِ ۴ را جلویش بگذار.**

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| `recursion` | ریکِرژن | تابعی که در تعریفِ خودش، خودش را صدا می‌زند |
| base case | بیس کِیس | کوچک‌ترین حالتی که جوابش بدونِ فراخوانیِ دوباره معلوم است |
| recursive step | ریکِرسیو استپ | گامی که مسئله را به نسخهٔ کوچک‌ترِ خودش تبدیل می‌کند |
| `call stack` | کال استَک | انباشتهٔ فراخوانی‌های تمام‌نشده، با انضباطِ `LIFO` |
| `nonlocal` | نان‌لوکال | اعلامِ اینکه یک تابعِ درونی می‌خواهد متغیرِ تابعِ بیرونی را **عوض** کند، نه فقط بخواند |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: دو تکهٔ اجباریِ هر تابعی که خودش را صدا می‌زند چیست، و اگر گامِ بازگشتی مسئله را کوچک نکند چه اتفاقی می‌افتد؟

**تمرینِ اجباری:** تابعِ `reverse_text(text)` را با `recursion` بنویس که یک رشته را وارونه کند، و نسخهٔ حلقه‌ای‌اش را هم بنویس. **اول با `==` ثابت کن جوابشان یکی است**، بعد برای هر دو جدولِ چهار اندازه‌ای بگیر. **سؤالِ اصلی: ستونِ نسبتِ نسخهٔ `recursion`دار چه عددی می‌دهد و چرا؟** جوابت باید بگوید کدام عملیاتِ داخلِ تابع مقصر است — و اگر نسبت `4` درآمد، همان بحثِ بخشِ ۴ است.

**تمرینِ ستاره‌دار ⭐:** با `recursion` تابعی بنویس که بزرگ‌ترین عضوِ یک `list` را پیدا کند، **بدونِ برش**. حالا **قبل از اجرا پیش‌بینی کن** بیشترین `n`ی که با سقفِ پیش‌فرضِ پایتون از پسش برمی‌آید چند است، و بنویس پیش‌بینی‌ات را از کجا آورده‌ای. بعد با یک جست‌وجوی دوبرابری پیدایش کن و **خطای پیش‌بینی‌ات را بنویس**. سؤالِ آخر: **این عدد روی ماشینِ دیگری همین است یا نه، و چرا؟**

## در فصل بعد

`recursion`ی که تا این‌جا دیدیم در هر فراخوانی **یک بار** خودش را صدا می‌زند. فصلِ بعد تابعی می‌سازد که **دو بار** صدا می‌زند، و همان یک تفاوت همه‌چیز را عوض می‌کند: برای یک ورودیِ کوچکِ ۲۴تایی، **۱۵۰٬۰۴۹ فراخوانی**.

بعد می‌بینیم چرا: **`fib(2)` در آن درخت ۲۸٬۶۵۷ بار حساب می‌شود.** با یک `dict` جلوی این تکرار را می‌گیریم و همان عدد به **۴۷** می‌رسد — و ستونِ نسبتِ فراخوانی از انفجار به `2.00` برمی‌گردد.

</div>

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