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

مفهوم بازگشت(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

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