بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 17: بازگشت Recursion

تابع بازگشتی مسئله را به نسخه‌ی کوچک‌تری از خودش می‌شکند؛ حالت پایه، پشته‌ی فراخوانی، مقایسه با حلقه و 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

مثال‌های این جلسه

چالش‌ها

  1. Recursive Factorial (آسان)
  2. Digit Sum (آسان)
  3. Reverse String (آسان)
  4. Fast Power (متوسط)
  5. Flatten Nested List (متوسط)
  6. Memoized Fibonacci (متوسط)
  7. Recursive Binary Search (متوسط)
  8. Directory Size (سخت)
  9. Cached Stair Climbing (سخت)
  10. Permutations (سخت)
  11. Nesting Depth (متوسط)
  12. Towers of Hanoi (سخت)

بیشتر بخوان

← جلسه‌ی 16: تابع‌های مرتبه‌بالا جلسه‌ی 18: پروژه: جعبه‌ابزار آمار متن →