بازگشت (Recursion)
«بازگشت در پایتون» یعنی وقتی یک «تابع (Function)» خودش را صدا می زند. این کار شبیه راه پله است؛ هر پله ما را نزدیک تر می کند. اما حواسمان باید جمع باشد تا بی نهایت پایین نرویم.
تعریف بازگشت و ایده اصلی
بازگشت روشی رایج در ریاضی و برنامه نویسی است. با آن روی داده ها قدم به قدم حرکت می کنی تا نتیجه برسد.
def countdown(n):
if n <= 0:
print("Done!")
else:
print(n)
countdown(n - 1)
countdown(5)
هشدار: اگر شرط توقف نگذاری، تابع همیشه خودش را صدا می زند.
شرط پایه و گام بازگشتی
هر تابع بازگشتی دو بخش دارد: «شرط پایه (Base Case)» برای توقف، و «گام بازگشتی (Recursive Case)» برای نزدیک شدن به توقف.
def factorial(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case
else:
return n * factorial(n - 1)
print(factorial(5))
نکته: شرط پایه باید بالاخره برقرار شود؛ وگرنه خطای پشته رخ می دهد.
دنباله فیبوناچی با بازگشت
در فیبوناچی، هر عدد جمع دو عدد قبلی است. با بازگشت می توان مقدار جایگاه دلخواه را حساب کرد.
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(7))
کار با لیست ها به صورت بازگشتی
می توان لیست را عضو به عضو پردازش کرد. هر بار یک تکه کوچک تر می شود.
def sum_list(numbers):
if len(numbers) == 0:
return 0
else:
return numbers[0] + sum_list(numbers[1:])
my_list = [1, 2, 3, 4, 5]
print(sum_list(my_list))
def find_max(numbers):
if len(numbers) == 1:
return numbers[0]
else:
max_of_rest = find_max(numbers[1:])
return numbers[0] if numbers[0] > max_of_rest else max_of_rest
my_list = [3, 7, 2, 9, 1]
print(find_max(my_list))
محدودیت عمق بازگشت در پایتون
پایتون برای عمق بازگشت حدی دارد؛ معمولاً نزدیک 1000. این کار از پرشدن پشته جلوگیری می کند.
import sys
print(sys.getrecursionlimit())
می توانی حد را بالاتر ببری؛ اما با احتیاط. افزایش بی جا باعث کرش می شود.
import sys
sys.setrecursionlimit(2000)
print(sys.getrecursionlimit())
هشدار: برای عمق های خیلی زیاد، راه تکراری بهتر است. بازگشت را فقط وقتی لازم است استفاده کن.
گام های عملی
- یک شمارش معکوس بازگشتی بنویس و اجرا کن.
- برای فاکتوریل، شرط پایه مشخص کن.
- فیبوناچی را با بازگشت محاسبه کن.
- جمع لیست را بازگشتی پیاده سازی کن.
جمع بندی سریع
- بازگشت یعنی تابع، خودش را صدا بزند.
- همیشه شرط پایه لازم است.
- هر بار به توقف نزدیک تر شو.
- عمق زیاد خطرناک است.
نکته: برای روش های دیگر، صفحه لانبدا و بعداً جنریتورها را ببین.