توابع بازگشتی (Recursion) در پایتون
تابع بازگشتی، تابعی است که خودش را در بدنه‌اش فراخوانی می‌کند. این روش زمانی مفید است که مسئله را بتوان به مسائل کوچک‌تر با ساختار مشابه تقسیم کرد. درک مفاهیم بازگشتی برای درک بهتر ساختار داده‌های بازگشتی مانند درخت‌ها و الگوریتم‌هایی مثل جستجوی دودویی یا پیمایش گراف‌ها ضروری است.
مثال ساده: شمارش معکوس
به جای استفاده از یک حلقه `for` برای شمارش معکوس، می‌توان از تابع بازگشتی استفاده کرد:
def countdown(n):
if n == 0:
print("Done!")
else:
print(n)
countdown(n - 1)
countdown(5)
خروجی:
5
4
3
2
1
Done!
مقایسه با حلقه for
همین عملکرد را می‌توان با یک حلقه `for` هم نوشت:
for i in range(5, 0, -1):
print(i)
print("Done!")
در اینجا، حلقه `for` به صورت بهینه‌تر و با مصرف حافظه‌ی کمتر عمل می‌کند، چون هر بار اجرای بازگشتی یک لایه جدید به پشته‌ی فراخوانی اضافه می‌کند. بنابراین:
- استفاده از `for` برای مسائل ساده معمولاً سریع‌تر و بهینه‌تر است.
- از بازگشت معمولاً زمانی استفاده می‌شود که الگوریتم به‌صورت طبیعی بازگشتی باشد (مثل پیمایش درخت).
مثال کلاسیک: فاکتوریل
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5))
خروجی:
120
اگر مورد پایه (Base Case) فراموش شود
فراموش‌کردن شرط توقف می‌تواند منجر به خطای پشته یا crash شدن برنامه شود:
def factorial(n):
return n * factorial(n - 1)
print(factorial(5))
خروجی:
RuntimeError: maximum recursion depth exceeded
بازگشت غیرمستقیم
در بازگشت غیرمستقیم، یک تابع تابع دیگری را فراخوانی می‌کند که آن تابع نیز تابع اول را صدا می‌زند. مثال:
def is_even(n):
if n == 0:
return True
else:
return is_odd(n - 1)
def is_odd(n):
return not is_even(n)
print(is_odd(17)) # True
print(is_even(23)) # False
چه زمانی از recursion استفاده کنیم؟
از recursion معمولاً زمانی استفاده می‌شود که ساختار داده بازگشتی (مثل درخت یا گراف) وجود دارد یا الگوریتم ذاتاً بازگشتی است (مثل فاکتوریل، فیبوناچی، یا حل معماهایی مانند Tower of Hanoi). در مسائل ساده یا تکراری معمولی بهتر است از حلقه استفاده شود تا از خطای حافظه جلوگیری شود.