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

آخر این فصل میتوانی:
- درختِ فراخوانیِ یک
recursionرا بکشی و گرههایش را بشماری - تشخیص بدهی کِی یک
recursionدارد کارِ تکراری انجام میدهد - با یک
dictدستی،memoisationبنویسی و اثرش را با شمارش نشان بدهی - بگویی چرا حتی نسخهٔ سریع هم یک هزینهٔ حافظه دارد که در جدولِ زمان دیده نمیشود
قبل از شروع#
از فصلِ ۱: حالتِ پایه، گامِ بازگشتی، call stack و پیامِ RecursionError.
از ترمِ ۱ فصلِ ۵: قاعدهٔ خواندنِ ستونِ نسبت — و مخصوصاً آخرین سطرش: «بزرگتر از 4 و رو به انفجار: نسبت خودش هم با n بزرگ میشود». این فصل اولین جایی است که آن سطر را در یک کدِ واقعی میبینی.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | کمتر از یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. یک تابع، و دو فراخوانی بهجای یکی#
دنبالهٔ فیبوناچی خودش را در تعریفِ خودش بهکار میبرد: هر عدد جمعِ دو عددِ قبلی است، و دو عددِ اول ۰ و ۱ هستند. این تعریف را مو به مو به کد تبدیل میکنیم.
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)
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)
این شکل یک درخت است و اسمش هم همین است: درختِ فراخوانی. هر گره یک فراخوانی است و فرزندانش فراخوانیهایی که خودش راه انداخته.
حالا با چشم بشمار: fib(3) دو بار در این درخت هست و fib(2) سه بار. هر کدامشان هم شاخههای خودشان را دوباره از صفر میسازند. هیچ چیزی نگه داشته نمیشود، چون هیچجا گفته نشده نگه داشته شود.
۲. شمردنِ گرهها#
🤔 اول حدس بزن: اگر
nرا دو برابر کنیم، تعدادِ فراخوانی چند برابر میشود؟ یک عدد بنویس، بعد جدول را ببین. (اگر گفتی «۲ یا ۴»، درست همان جایی هستی که این فصل میخواهد.)
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")
fib(5) = 5 · فراخوانی: 15
n فراخوانی نسبت به سطر قبل
3 5 —
6 25 5.00
12 465 18.60
24 150,049 322.69
5.00، بعد 18.60، بعد 322.69. ستونِ نسبت به عددی نمیرسد که آنجا بماند؛ خودش هم منفجر میشود. این دقیقاً همان امضایی است که ترمِ ۱ فصلِ ۵ برای رشدِ نمایی نوشت، و تنها مرتبهای است که این شکل را دارد.
نردبانِ ضربی اینجا حرفش را زد، ولی نردبانِ جمعی چیزِ دیگری هم نشان میدهد:
table([(n, fib_calls(n)[1]) for n in (20, 21, 22, 23, 24)], "فراخوانی", ",d")
n فراخوانی نسبت به سطر قبل
20 21,891 —
21 35,421 1.62
22 57,313 1.62
23 92,735 1.62
24 150,049 1.62
هر بار که فقط یکی به n اضافه میشود، کار در 1.62 ضرب میشود — و این عدد در هر چهار سطر یکی است. رشدِ نمایی همین است: در هر قدم، ضرب در یک عددِ ثابت. پایهاش اینجا اتفاقاً 2 نیست، 1.62 است؛ ولی شکلِ رشد همان است و همانقدر هم بیرحم.
🌱 ریشهاش کجاست: چرا ضرب شدنِ پیاپی در یک عددِ کوچک اینقدر زود از کنترل خارج میشود — و چرا شهودِ آدم تقریباً همیشه کمبرآوردش میکند — در ریشه ترمِ ۴ فصل ۷ با مثالِ ملموس ساخته شده. نکتهٔ کلیدی همانجاست: در رشدِ نمایی، بزرگیِ ضریب مهم نیست؛ ثابت بودنش مهم است.
۳. چرا: همان کار، بارها#
عدد 150,049 از جایی نیامده. آن را میشود شکافت.
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,} بار")
در 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 بار
fib(2) جوابش همیشه 1 است و ۲۸٬۶۵۷ بار از صفر حساب میشود.
منشأِ انفجار همین است، نه خودِ recursion. تابعِ فصلِ ۱ هم recursion داشت و خطی درآمد، چون هر فراخوانی مسئلهٔ تازهای حل میکرد. اینجا شاخهٔ چپ و شاخهٔ راست بخشِ بزرگی از کارشان مشترک است و هیچکدام از دیگری خبر ندارد.
۴. memoisation: هر جواب فقط یک بار#
راهِ حل به اندازهٔ مسئله ساده است: هر جوابی که حساب شد، در یک dict نگه دار؛ قبل از حساب کردن، اول آنجا را نگاه کن. اسمِ این کار memoisation است و کلِ ابزارش یک dict است.
💡 نکته: پایتون ابزارِ آمادهای هم دارد که همین کار را خودکار میکند. این دوره عمداً سراغش نمیرود و آن را دستی مینویسد، چون درسِ این فصل خودِ
dictو خودِ شمارش است، نه یک تزئینِ آماده. آن ابزار موضوعِ دورهٔ داربست است.
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]:,}")
جوابِ دو نسخه یکی است؟ True
در n = 24 · با memo: 47 · بدونِ memo: 150,049
در n = 30 · با memo: 59 · بدونِ memo: 2,692,537
۵۹ در برابرِ ۲٬۶۹۲٬۵۳۷ — بیش از چهلوپنج هزار برابر کمتر، با جوابِ کاملاً یکسان. و به سطرِ اول دقت کن: تفاوت با بزرگتر شدنِ n بازتر میشود، چون یکی خطی است و دیگری نمایی.
🤔 اول حدس بزن: ستونِ نسبتِ تعدادِ فراخوانیِ نسخهٔ
memoچه عددی میدهد؟ بنویسش، بعد جدول را ببین.
MEMO = [100, 200, 400, 800]
table([(n, fib_memo_calls(n)[1]) for n in MEMO], "فراخوانی", ",d")
n فراخوانی نسبت به سطر قبل
100 199 —
200 399 2.01
400 799 2.00
800 1,599 2.00
2.00 — یعنی O(n). از نمایی به خطی، فقط با یک dict. و منطقش را میشود در یک جمله نوشت: هر k بینِ ۰ و n دقیقاً یک بار واقعاً حساب میشود؛ بقیهٔ فراخوانیها فقط از dict میخوانند.
۵. هزینهای که در جدولِ فراخوانی دیده نمیشود#
نسخهٔ memo رایگان نیست. دو چیز نگه میدارد: خودِ dict، و عمقِ call stack.
table([(n, fib_memo_calls(n)[2]) for n in MEMO], "بیشترین عمق", ",d")
n بیشترین عمق نسبت به سطر قبل
100 100 —
200 200 2.00
400 400 2.00
800 800 2.00
عمق دقیقاً برابرِ n است و ستونِ نسبتش 2.00. یعنی حافظهای که این تابع مصرف میکند با n خطی بالا میرود — و برخلافِ زمان، این هزینه سقفِ سخت دارد، چون call stack سقف دارد.
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}")
سه نسخه یک جواب میدهند؟ True
تعدادِ رقمهای fib(10,000): 2090
RecursionError: maximum recursion depth exceeded
حلقه fib(10,000) را میدهد — عددی با ۲٬۰۹۰ رقم — و نسخهٔ memo روی همان ورودی میشکند. نه چون کند است؛ چون عمیق است. memoisation مرتبهٔ زمان را درست کرد و به مرتبهٔ حافظه دست نزد.
✅ چک کن:
MEMOرا به[50, 100, 200, 400]ببر و هر دو جدولِ این بخش را دوباره بگیر. ستونِ نسبتِ عمق باید دقیقاً2.00بماند و ستونِ نسبتِ فراخوانی2.01یا2.00— چون تعدادِ فراخوانی2n - 1است و آن «منهای یک» در اندازههای کوچکتر خودش را در رقمِ دوم نشان میدهد. سطرِ اولِ جدولِ عمق باید50شود. اگر عمق ثابت ماند، احتمالاًdepth + 1را جاییdepthنوشتهای و شمارنده اصلاً بالا نمیرود.
۶. دو اشتباهی که در نوشتنِ memo پیش میآید#
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}")
جوابش درست است؟ True
فراخوانی با این «memo» : 150,049
فراخوانی بدونِ memo اصلاً: 150,049
KeyError: 9
🔧 اگر کار نکرد: اشتباهِ اول هیچ پیامی ندارد و بدترینشان است. کد
if k in memoرا دارد، جوابِ درست میدهد، و دقیقاً همان ۱۵۰٬۰۴۹ فراخوانیِ نسخهٔ بدونِmemoرا انجام میدهد — چونmemoهیچوقت پر نمیشود. تنها راهِ گرفتنش همین است: شمارنده بگذار. اگر شمارنده نداشتی، فقط میگفتی «سریع نشد» و دنبالِ دلیلِ اشتباه میگشتی.اشتباهِ دوم صریح است:
KeyError: 9یعنی سراغِ کلیدِ9رفتهای و آنجا نبوده.memoیکcacheاست، نه یک جدولِ آماده — قبل از خواندن باید یا مطمئن شوی هست، یا با.getجوابِ نبودنش را هم پیشبینی کنی.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ سه نسخه از یک تابعِ واحد —
recursionساده،recursionباmemo، و حلقه — با جوابِ تأییدشدهٔ برابر. در کدام بازهٔn؟ ۳ تا ۳۰ برای نسخهٔ بدونِmemo(بالاتر از آن در چند دقیقه هم تمام نمیشود) و ۱۰۰ تا ۸۰۰ برای نسخهٔmemo، که سقفش را عمقِcall stackتعیین کرده. با چند تکرار، و کمینه یا میانگین؟ یک اجرا برای همه؛ هر عددِ این فصل یک شمارش است، نه یک زمان — و شمارش قطعی است.
🤖 از دستیارت بپرس: «چرا
recursionفیبوناچی اینقدر گران است ولیrecursionجمعِ یکlistنه؟» بعد این را هم بپرس: «اگرmemoرا به تابع بدهم ولی هیچوقت چیزی در آن نگذارم، چه اتفاقی میافتد؟» — جوابِ درست باید بگوید کد کار میکند و هیچ چیزی سریع نمیشود. اگر دستیارت گفت «خطا میدهد»، خروجیِ بخشِ ۶ را جلویش بگذار.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| call tree | کالتری | درختِ همهٔ فراخوانیهایی که یک فراخوانی راه میاندازد |
memoisation |
مموایزیشن | نگه داشتنِ جوابِ هر ورودی تا دوباره حساب نشود |
| overlapping subproblems | اورلپینگ سابپرابلمز | زیرمسئلههایی که بارها در درختِ فراخوانی تکرار میشوند |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
دو فصل شد که دربارهٔ خودِ recursion حرف زدیم. از فصلِ بعد سراغِ کاری میرویم که recursion در آن واقعاً برنده است — ولی اول باید ببینیم بدونش چه شکلی است.
فصلِ بعد دو مرتبسازی را با دست انجام میدهد و مقایسههایشان را میشمارد. هر دو O(n²) هستند: در n = 2,000 یکی 1,999,000 مقایسه میکند و دیگری 1,022,176. ولی وقتی ورودی از پیش مرتب باشد، دومی به 1,999 میافتد و ستونِ نسبتش 2.00 میشود — و اولی هنوز همان 1,999,000 است.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.