تابع بازگشتی (Recursive Function)

• تابعی که در تعریف خودش، خودش رو صدا می‌زنه

• برای مسائلی که می‌شه اونا رو به نسخه‌های کوچیک‌تر از خودشون تقسیم کرد مناسبه

• هر تابع بازگشتی باید دو بخش داشته باشه:

  • حالت پایه (Base Case): شرطی که بازگشت رو متوقف می‌کنه
  • حالت بازگشتی (Recursive Case): تابع خودش رو با ورودی کوچیک‌تر صدا می‌زنه

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))

120

• روند اجرا برای factorial(3):

factorial(3)
= 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * (2 * (1 * factorial(0)))
= 3 * (2 * (1 * 1))
= 6

هشدارنکته

اگه حالت پایه تعریف نشه یا هیچ‌وقت برقرار نشه، تابع بی‌نهایت خودش رو صدا می‌زنه و در نهایت خطای RecursionError می‌ده.

• مثال دیگه: دنباله فیبوناچی

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

print(fib(6))

8

مقایسه با حلقه (Loop)

• خیلی از مسائل بازگشتی رو می‌شه با حلقه هم حل کرد
• بازگشت معمولاً خواناتر ولی حلقه معمولاً بهینه‌تر (از نظر حافظه) هست

def factorial_recursive(n):
    if n == 0:
        return 1
    return n * factorial_recursive(n - 1)

def factorial_loop(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result