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

جلسه‌ی 33: تابعی که خودش را صدا می‌زند Recursion

با بازگشت آشنا می‌شویم: تابعی که برای حل یک مسئله‌ی بزرگ، خودش را برای یک نسخه‌ی کوچک‌تر صدا می‌زند.

در این جلسه یاد می‌گیری

درس

تا حالا تابع‌ها تابع‌های دیگر را صدا می‌زدند. ولی یک تابع می‌تواند «خودش» را هم صدا بزند! به این می‌گوییم بازگشت. مثل عروسک‌های روسی: داخل هر عروسک یک عروسک کوچک‌تر است.

def countdown(n):
    if n == 0:
        print("Go!")
    else:
        print(n)
        countdown(n - 1)

countdown(3)

هر تابع بازگشتی دو بخش دارد: «حالت پایه» که جایی است که دیگر خودش را صدا نمی‌زند و کار تمام می‌شود (اینجا n == 0)، و «قدم بازگشتی» که خودش را با یک مسئله‌ی کوچک‌تر صدا می‌زند (اینجا n - 1).

تابع بازگشتی می‌تواند جواب هم برگرداند. فاکتوریل ۵ یعنی 5 * 4 * 3 * 2 * 1. نکته‌ی جالب: فاکتوریل ۵ همان 5 ضربدر فاکتوریل ۴ است!

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

اگر حالت پایه را فراموش کنی چه می‌شود؟ تابع تا ابد خودش را صدا می‌زند! پایتون بعد از حدود هزار بار صدا زدن جلویش را می‌گیرد و خطای RecursionError می‌دهد. نترس؛ این یعنی فقط باید حالت پایه را اضافه کنی یا مطمئن شوی مسئله واقعاً کوچک‌تر می‌شود.

def oops(n):
    return oops(n - 1)

# oops(5) would stop with RecursionError

جمع رقم‌های یک عدد: رقم آخر با n % 10 و بقیه‌ی عدد با n // 10 به دست می‌آید. پس جمع رقم‌ها = رقم آخر + جمع رقم‌های بقیه.

def sum_digits(n):
    if n < 10:
        return n
    return n % 10 + sum_digits(n // 10)

print(sum_digits(472))

توان هم بازگشتی می‌شود: 2 به توان 5 یعنی 2 ضربدر 2 به توان 4. و هر عددی به توان 0 می‌شود 1؛ این حالت پایه است.

def power(base, exp):
    if exp == 0:
        return 1
    return base * power(base, exp - 1)

print(power(2, 5))

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

چالش‌ها

  1. Rocket Countdown (آسان)
  2. Count Up (آسان)
  3. Factorial (آسان)
  4. Digit Sum (متوسط)
  5. Power Up (متوسط)
  6. Add Them Up (متوسط)
  7. Shrinking Stars (متوسط)
  8. Backwards (سخت)
  9. Rabbit Numbers (سخت)
  10. Letter Counter (سخت)
  11. Palindrome (متوسط)
  12. Greatest Divisor (سخت)
  13. Binary Code (سخت)
  14. Biggest by Recursion (سخت)

بیشتر بخوان

← جلسه‌ی 32: مرتبش کن! جلسه‌ی 34: شبیه‌سازی با شانس →