جلسهی 33: تابعی که خودش را صدا میزند Recursion
با بازگشت آشنا میشویم: تابعی که برای حل یک مسئلهی بزرگ، خودش را برای یک نسخهی کوچکتر صدا میزند.
در این جلسه یاد میگیری
- در پایان این جلسه میتوانم تابعی بنویسم که خودش را صدا بزند.
- در پایان این جلسه میدانم «حالت پایه» چیست و چرا لازم است.
- در پایان این جلسه میتوانم فاکتوریل، جمع رقمها و توان را بازگشتی حساب کنم.
- در پایان این جلسه میفهمم
RecursionErrorیعنی چه و چطور درستش کنم.
درس
تا حالا تابعها تابعهای دیگر را صدا میزدند. ولی یک تابع میتواند «خودش» را هم صدا بزند! به این میگوییم بازگشت. مثل عروسکهای روسی: داخل هر عروسک یک عروسک کوچکتر است.
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))مثالهای این جلسه
- مثال تابع در پایتون: def countdown(n):
- مثال تابع در پایتون: def factorial(n):
- مثال تابع در پایتون: def oops(n):
- مثال تابع در پایتون: def sum_digits(n):
- مثال تابع در پایتون: def power(base, exp):
چالشها
- Rocket Countdown (آسان)
- Count Up (آسان)
- Factorial (آسان)
- Digit Sum (متوسط)
- Power Up (متوسط)
- Add Them Up (متوسط)
- Shrinking Stars (متوسط)
- Backwards (سخت)
- Rabbit Numbers (سخت)
- Letter Counter (سخت)
- Palindrome (متوسط)
- Greatest Divisor (سخت)
- Binary Code (سخت)
- Biggest by Recursion (سخت)