در این فصل چه یاد میگیری#
تا اینجای دوره هر کاری با حلقه انجام شده. این فصل ابزارِ دومی میآورد که بعضی مسئلهها با آن کوتاهتر و روشنتر نوشته میشوند: تابعی که خودش را صدا میزند.
و بلافاصله هزینهاش را هم میشماریم. جمعِ یک list با ۴٬۰۰۰ عضو، ۴٬۰۰۱ فراخوانی میخواهد و ستونِ نسبتش 2.00 است. ولی اگر همان تابع را با برش بنویسی — که طبیعیترین شکلِ نوشتنش هم هست — ۷٬۹۹۸٬۰۰۰ عضو کپی میشود و ستونِ نسبت 4.00. و روی یک list با ۲۰۰٬۰۰۰ عضو، recursion اصلاً اجرا نمیشود: پایتون با یک پیامِ مشخص جلویش را میگیرد.
آخر این فصل میتوانی:
- تابعی بنویسی که خودش را صدا میزند، با حالتِ پایه و گامِ بازگشتی
- بگویی
call stackچیست و چرا عمقش یک منبعِ محدود است RecursionErrorرا بخوانی و بفهمی چه چیزی را گزارش میکند- هر
recursionرا به یک حلقه برگردانی و برابریِ جواب را ثابت کنی
قبل از شروع#
از ترمِ ۲ فصلِ ۷: انضباطِ LIFO — آخرین چیزی که گذاشتی، اولین چیزی است که برمیداری. آن فصل stack را با list ساخت؛ این فصل نشان میدهد پایتون خودش یکی دارد.
از ترمِ ۲ فصلِ ۵: قاعدهٔ تشخیصِ O(n²) — یک عملِ O(n) داخلِ حلقهای که n بار میچرخد. بخشِ ۳ همان قاعده را در جایی پیدا میکند که اصلاً حلقهای در کار نیست.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | کمتر از یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. کوچکترین نسخهٔ ممکن، با دست#
جمعِ یک list را میشود اینطور تعریف کرد: جمعِ کلِ فهرست یعنی عضوِ اول، بهعلاوهٔ جمعِ بقیهاش. این تعریف به خودش ارجاع میدهد و همانطور که هست به کد تبدیل میشود — به شرطی که بگوییم کِی باید بایستد.
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]))
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
به شکلِ خروجی نگاه کن: اول همهچیز تو میرود، بعد همهچیز برمیگردد. پنج فراخوانی رفتند تا ته، و بعد جوابها یکییکی به بالا پس داده شدند.
هر تابعی که خودش را صدا میزند دقیقاً دو تکه دارد و هیچکدامشان اختیاری نیست:
- حالتِ پایه — کوچکترین حالتی که جوابش را بدونِ صدا زدنِ خودمان میدانیم. اینجا: فهرستِ خالی، جمع صفر.
- گامِ بازگشتی — مسئله را به یک مسئلهٔ کوچکتر از همان جنس تبدیل میکند. اینجا: یک عضو کمتر.
شرطِ کار کردن هم روشن است: گامِ بازگشتی باید مسئله را به حالتِ پایه نزدیک کند. اگر نکند، هیچوقت نمیایستد.
۲. حالتِ پایه را بردار#
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}")
IndexError: list index out of range
RecursionError: maximum recursion depth exceeded
🔧 اگر کار نکرد: دو تابعِ معیوب، دو پیامِ کاملاً متفاوت.
sum_no_baseبه فهرستِ خالی میرسد و چون کسی نگفته آنجا بایستد،values[0]را روی چیزی صدا میزند که عضوی ندارد:IndexError. این خطا دربارهٔrecursionهیچ چیزی نمیگوید و همین گمراهکننده است — دنبالِ اشکالِ اندیس میگردی، در حالی که اشکال نبودِ حالتِ پایه است.
countdownهیچوقت به هیچ مرزی نمیرسد و پایتون خودش جلویش را میگیرد:RecursionError: maximum recursion depth exceeded. این پیام تقریباً همیشه یک معنی دارد: یا حالتِ پایه نداری، یا گامِ بازگشتیات به آن نزدیک نمیشود. اولین کاری که باید بکنی این است که بپرسی «چه چیزی در هر فراخوانی کوچکتر میشود؟» — اگر جوابی نداشتی، پیدایش کردهای.
۳. call stack: همان LIFO، این بار مالِ پایتون#
چرا پایتون سقف دارد؟ چون هر فراخوانی که تمام نشده باید یادش بماند: کدام تابع بود، متغیرهایش چه بودند، و بعد از برگشتن باید کجا ادامه بدهد. این یادداشتها روی هم انباشته میشوند و دقیقاً همان انضباطِ LIFOی ترمِ ۲ فصلِ ۷ را دارند: آخرین فراخوانی اولین چیزی است که تمام میشود. اسمِ این انباشته call stack است.
def deepest():
"""تا جایی که پایتون اجازه بدهد پایین میرود و عمقِ رسیده را برمیگرداند."""
def down(depth):
try:
return down(depth + 1)
except RecursionError:
return depth
return down(1)
print("سقفِ اعلامشدهٔ پایتون:", sys.getrecursionlimit())
print("عمقی که واقعاً رسیدیم :", deepest())
سقفِ اعلامشدهٔ پایتون: 1000
عمقی که واقعاً رسیدیم : 998
عددِ دوم همیشه کمی کمتر از اولی است، چون وقتی deepest صدا زده میشود چند فراخوانی از قبل روی call stack نشستهاند و سهمشان را برداشتهاند. عددِ تو ممکن است یکیدو تا فرق کند؛ چیزی که فرق نمیکند وجودِ سقف است.
⚠️ مواظب باش:
sys.setrecursionlimitاین سقف را بالا میبرد و کارِ بیخطری نیست. سقفْ محافظِ توست: با عددِ خیلی بزرگ، بهجای یک استثنای تمیز، کلِ نشستِ Colab بدونِ هیچ پیامی میمیرد و هر چه در حافظه داشتی از دست میرود. هر جای این ترم که لازمش داریم، عددِ محافظهکارانه میگذاریم و میگوییم چرا.
۴. یک O(n²) که هیچ حلقهای ندارد#
نسخهٔ بخشِ ۱ یک اشکالِ پنهان دارد. values[1:] یک list تازه میسازد و همهچیز را در آن کپی میکند — و این کار در هر فراخوانی تکرار میشود. نسخهٔ دوم بهجای برش، یک اندیس جلو میبرد.
یک کلمهٔ تازه در کدِ بعدی هست که باید قبلش گفته شود: nonlocal. یک تابعِ درونی، متغیرهای تابعِ بیرونی را میخواند بدونِ هیچ اعلامی؛ ولی اگر بخواهد بنویسدشان، پایتون بهجای نوشتن یک متغیرِ تازهٔ محلی میسازد و بیرونی دستنخورده میماند. nonlocal copied دقیقاً یک جمله میگوید: «این همان copiedِ بیرونی است، میخواهم خودش را عوض کنم.» از اینجا به بعدِ ترم، هر شمارندهای که داخلِ یک تابعِ تودرتو بالا میرود همین یک خط را لازم دارد.
🤔 اول حدس بزن: ستونِ نسبتِ «تعدادِ عضوی که نسخهٔ برشی کپی میکند» چه عددی میدهد؟ جوابت را بنویس، بعد جدول را ببین. (راهنمایی: قاعدهٔ تشخیصِ ترمِ ۲ فصلِ ۵ را روی این کد بهکار ببر.)
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]))
جوابِ دو نسخه یکی است؟ True
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")
n عضوِ کپیشده نسبت به سطر قبل
500 124,750 —
1,000 499,500 4.00
2,000 1,999,000 4.00
4,000 7,998,000 4.00
4.00 — یعنی O(n²)، در تابعی که یک خط حلقه هم ندارد.
قاعدهٔ ترمِ ۲ فصلِ ۵ میگفت «یک عملِ O(n) داخلِ حلقهٔ nتایی». اینجا حلقهای نیست، ولی recursion خودش همان حلقه است: n فراخوانی، و در هر کدام یک برشِ O(n). قاعده هیچ تغییری نکرده، فقط حلقه اسمِ دیگری دارد.
حالا همان کار، با اندیس بهجای برش:
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")
n فراخوانی نسبت به سطر قبل
500 501 —
1,000 1,001 2.00
2,000 2,001 2.00
4,000 4,001 2.00
2.00 — یعنی O(n)، با همان جواب. یک نویسه اختلاف در نحوهٔ نوشتن، دو مرتبهٔ متفاوت.
✅ چک کن:
LADDERرا به[250, 500, 1_000, 2_000]ببر و فقط جدولِ کپی را دوباره بگیر. سطرِ اول باید31,125بدهد و ستونِ نسبت باید هنوز4.00بماند. اگر نسبت2.00شد، احتمالاًrest = vals[1:]را بهrest = valsتبدیل کردهای — و آنوقت کدت اصلاً تمام نمیشود، پس قبلشRecursionErrorمیگیری.
۵. هر recursion را میشود به حلقه برگرداند#
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}")
جوابِ حلقه با جوابِ 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
هر دو نسبتِ 2 میدهند — مرتبهشان یکی است. ولی روی این ماشین recursion نزدیک به هشت برابر کندتر درآمد. عددهای تو فرق میکنند؛ این نسبت نباید فرق کند، چون دلیلش ساختاری است: هر فراخوانی یک قابِ تازه روی call stack میسازد و جمع کردنِ دو عدد در مقایسه با آن تقریباً رایگان است. این همان ثابتِ پنهانِ ترمِ ۱ فصلِ ۹ است، این بار بهشکلِ هزینهٔ فراخوانی.
و یک تفاوتِ سختتر هم هست:
big = list(range(200_000))
print("حلقه روی ۲۰۰٬۰۰۰ عضو:", sum_loop(big))
try:
sum_index(big)
except RecursionError as err:
print(f"{type(err).__name__}: {err}")
حلقه روی ۲۰۰٬۰۰۰ عضو: 19999900000
RecursionError: maximum recursion depth exceeded
حلقه هیچ سقفی ندارد و recursion دارد. پس قاعدهٔ عملی این است: اگر عمقِ فراخوانی با n بزرگ میشود، recursion انتخابِ درستی نیست. جمعِ یک فهرست دقیقاً همین است و برای همین کسی آن را با recursion نمینویسد.
پس recursion اصلاً برای چه خوب است؟ برای مسئلههایی که تعریفِ خودشان recursion دارد و عمقشان log n است، نه n. فصلهای ۴ و ۵ دو تای مهمترینشان را میسازند و آنجا عمق در حدِ چند ده میماند، نه چند هزار.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ سه نسخه از یک کارِ واحد —
recursionبا برش،recursionبا اندیس، و حلقه — با ورودیِ کاملاً یکسان و جوابِ تأییدشدهٔ برابر. در کدام بازهٔn؟ ۵۰۰ تا ۴٬۰۰۰، که سقفش را عمقِcall stackتعیین کرده نه صبرِ ما. با چند تکرار، و کمینه یا میانگین؟ جدولِ کپی و جدولِ فراخوانی یک اجرا، چون شمارشاند و قطعی؛ جدولِ زمان سه تکرار بهعلاوهٔ گرمکننده، کمینه.
🤖 از دستیارت بپرس: «تفاوتِ حالتِ پایه و گامِ بازگشتی را با یک مثال بگو.» بعد این را هم بپرس: «چرا
sum_sliceمرتبهاشO(n²)است ولیsum_indexنه؟» — جوابِ درست باید به کپیِ برش برسد، نه به تعدادِ فراخوانی. اگر دستیارت گفت «هر دوO(n)هستند»، جدولِ بخشِ ۴ را جلویش بگذار.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
recursion |
ریکِرژن | تابعی که در تعریفِ خودش، خودش را صدا میزند |
| base case | بیس کِیس | کوچکترین حالتی که جوابش بدونِ فراخوانیِ دوباره معلوم است |
| recursive step | ریکِرسیو استپ | گامی که مسئله را به نسخهٔ کوچکترِ خودش تبدیل میکند |
call stack |
کال استَک | انباشتهٔ فراخوانیهای تمامنشده، با انضباطِ LIFO |
nonlocal |
نانلوکال | اعلامِ اینکه یک تابعِ درونی میخواهد متغیرِ تابعِ بیرونی را عوض کند، نه فقط بخواند |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
recursionی که تا اینجا دیدیم در هر فراخوانی یک بار خودش را صدا میزند. فصلِ بعد تابعی میسازد که دو بار صدا میزند، و همان یک تفاوت همهچیز را عوض میکند: برای یک ورودیِ کوچکِ ۲۴تایی، ۱۵۰٬۰۴۹ فراخوانی.
بعد میبینیم چرا: fib(2) در آن درخت ۲۸٬۶۵۷ بار حساب میشود. با یک dict جلوی این تکرار را میگیریم و همان عدد به ۴۷ میرسد — و ستونِ نسبتِ فراخوانی از انفجار به 2.00 برمیگردد.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.