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