آموزش تابع بازگشتی در پایتون

مفهوم بازگشت(Recursion)

بازگشت، وقتی اتفاق می‌افتد که یک تابع خودش را فراخوانی کند(صدا بزند). روشِ بازگشتی، یک مفهوم متداول در ریاضیات و برنامه‌نویسی است. این یعنی اینکه یک تابع خودش را صدا بزند. مزیت تابع بازگشتی این است که با استفاده از آن می‌توانیم روی داده‌ها، برای رسیدن به یک نتیجه حلقه بزنیم. برنامه‌نویس باید در استفاده از توابع بازگشتی بسیار دقت کند، زیرا با استفاده از آن، به راحتی می‌تواند تابعی بنویسد که هرگز خاتمه پیدا نمی کند، یا تابعی بنویسد که از حافظه یا پردازنده‌ی رایانه زیاد استفاده کند. اما وقتی که تابع بازگشتی به درستی نوشته شود، می‌تواند بسیار موثر باشد و با رویکرد زیبای ریاضی، در برنامه نویسی استفاده شود. 

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

countdown(5)

5
4
3
2
1
Done!

شرط پایه(Base Case) و شرط بازگشتی(Recursive Case)

هر تابع بازگشتی در پایتون باید دو شرط داشته باشد:

1. یک شرط پایه: یک شرط که بازگشت را متوقف می‌کند. 
2. یک شرط بازگشتی: یک شرط که با استفاده از آن، تابع، خودش را با یک آرگومان اصلاح شده فراخوانی می‌کند(صدا می‌زند).

اگر شرط پایه را مشخص نکنیم، این تابع برای همیشه خودش را فراخوانی می‌کند و باعث خطای سرریز پشته(stack overflow) می‌شود.

def factorial(n):
  # شرط پایه
  if n == 0 or n == 1:
    return 1
  # شرط بازگشتی
  else:
    return n * factorial(n - 1)

print(factorial(5))

120

شرط پایه(base case) بسیار مهم است. همواره مطمئن شوید که تابع بازگشتی شما یک شرط داشته باشد که سرانجام تحقق پیدا کند. 

دنباله‌ی فیبوناچی(Fibonacci)

دنباله‌ی فیبوناچی، یک مثال قدیمی است که در آن، هر عدد، از جمع دو عددِ قبلیِ آن به دست می‌آید. این دنباله با اعداد 0 و 1 شروع می‌شود:

0, 1, 1, 2, 3, 5, 8, 13, ...

این دنباله به طور نامحدود ادامه می‌یابد؛ و هر عدد در آن از جمع دو عدد قبلی به دست می‌آید. ما می‌توانیم از توابع بازگشتی برای پیدا کردن یک عدد خاص در این دنباله استفاده کنیم. 

def fibonacci(n):
  if n <= 1:
    return n
  else:
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(7))

13

استفاده از لیست‌ها به همراه تابع بازگشتی

در پردازش لیست‌ها، می‌توانیم از تابع بازگشتی استفاده کنیم تا در هر دفعه یک عنصر را مدیریت کنیم:

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))

15

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))

9

محدوده‌ی تکرار تابع بازگشتی

پایتون روی تعداد دفعاتی که تابع بازگشتی می‌تواند تکرار شود، محدودیت(limit) دارد. حد پیش فرض برای فراخوانی تابع بازگشتی، 1000 دور می‌باشد. 

import sys
print(sys.getrecursionlimit())

1000

اگر نیاز دارید تابع بازگشتی را به تعداد بیشتر(از 1000) تکرار کنید، می‌توانید حد(limit) آن را افزایش دهید؛ اما مراقب باشید زیرا این کار می‌تواند باعث توقف و خرابی سیستم(crash) شود. 

import sys
sys.setrecursionlimit(2000)
print(sys.getrecursionlimit())

افزایش محدودیت تابع بازگشتی باید با احتیاط انجام شود. برای تابع‌های بازگشتی که نیاز به تکرارهای بسیار زیاد دارند، به جای لیست‌ها، از تکرارگرها(Iterators) استفاده کنید. 

منبع: www.w3schools.com/python