جلسهی 17: بازگشت Recursion
تابع بازگشتی مسئله را به نسخهی کوچکتری از خودش میشکند؛ حالت پایه، پشتهی فراخوانی، مقایسه با حلقه و memoization را دقیق بررسی میکنیم.
در این جلسه یاد میگیری
- تابع بازگشتی با حالت پایه (
base case) و حالت بازگشتی درست بنویسی. - پشتهی فراخوانی (
call stack) و محدودیت عمق بازگشت در پایتون را بشناسی. - ساختارهای تودرتو مثل لیستهای تودرتو و درخت پوشهها را با بازگشت پیمایش کنی.
- با دیکشنری یا
functools.lru_cacheاز محاسبهی تکراری جلوگیری کنی (memoization).
درس
تابع بازگشتی خودش را صدا میزند. دو جزء لازم دارد: حالت پایه که بدون بازگشت جواب میدهد، و حالت بازگشتی که مسئله را کوچکتر میکند تا حتماً به حالت پایه برسد.
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1)
print(factorial(5)) # 120هر فراخوانی یک قاب (frame) روی پشتهی فراخوانی میسازد که تا برگشتن جوابش باقی میماند. پایتون عمق را محدود میکند (پیشفرض حدود ۱۰۰۰) و پس از آن RecursionError میدهد؛ پایتون بهینهسازی tail call ندارد.
import sys
print(sys.getrecursionlimit())
def depth(n):
return 0 if n == 0 else 1 + depth(n - 1)
print(depth(500))جایی که بازگشت واقعاً میدرخشد دادهی تودرتوست: لیست داخل لیست، دیکشنری داخل دیکشنری، درخت فایلها. ساختار کد همان ساختار داده است.
def total(data):
if isinstance(data, list):
return sum(total(item) for item in data)
return data
print(total([1, [2, [3, 4]], 5])) # 15هر بازگشتی را میتوان با حلقه (و در صورت نیاز یک پشتهی دستی) نوشت. برای شمارش ساده یا پیمایش خطی حلقه سریعتر و امنتر است؛ بازگشت را برای مسئلههای ذاتاً درختی یا «تقسیم و غلبه» نگه دار.
def factorial_iter(n):
result = 1
for k in range(2, n + 1):
result *= k
return result
print(factorial_iter(5))fib بازگشتی ساده زیرمسئلههای یکسان را میلیونها بار دوباره حساب میکند. memoization جوابها را ذخیره میکند: با یک دیکشنری دستی، یا با دکوراتور functools.lru_cache که همین کار را خودکار انجام میدهد.
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(80)) # 23416728348467685مثالهای این جلسه
- مثال تابع در پایتون: def factorial(n): — بازگشت
- مثال تابع در پایتون: def depth(n):
- مثال تابع در پایتون: def total(data):
- مثال تابع در پایتون: def factorial_iter(n):
- مثال تابع در پایتون: def fib(n):
چالشها
- Recursive Factorial (آسان)
- Digit Sum (آسان)
- Reverse String (آسان)
- Fast Power (متوسط)
- Flatten Nested List (متوسط)
- Memoized Fibonacci (متوسط)
- Recursive Binary Search (متوسط)
- Directory Size (سخت)
- Cached Stair Climbing (سخت)
- Permutations (سخت)
- Nesting Depth (متوسط)
- Towers of Hanoi (سخت)
بیشتر بخوان
← جلسهی 16: تابعهای مرتبهبالا جلسهی 18: پروژه: جعبهابزار آمار متن →