توابع بازگشتی یا recursion

توابع recursion یا بازگشتی

recursion یک مفهوم بسیار مهم در برنامه نویسی کاربردی است. بخش اساسی recursion خود ارجاع است - توابع خود را فراخوانی می کنند. این برای حل مسائل مورد استفاده قرار می گیرد که می تواند به مشکلاتی ساده تر و کوچکتر از همان نوع شکسته شود. مثال کلاسیک از یک تابع که به صورت بازگشتی اجرا می شود، تابع فاکتوریل است که خروجی تمام عدد صحیح مثبت ، در زیر یک عدد مشخص را می یابد. به عنوان مثال، 5! (5 فاکتوریل) 5 * 4 * 3 * 2 * 1 (120) است. برای پیاده سازی این رابطه بازگشتی، توجه کنید که 5! = 5 * 4 !، 4! = 4 * 3 !، 3! = 3 * 2! و غیره به طور کلی، n! = n * (n-1)! علاوه بر این، 1! = 1. این به عنوان مورد پایه شناخته می شود، زیرا می توان بدون انجام فاکتوریل های بیشتر محاسبه کرد. در زیر اجرای مجدد تابع فاکتوریل قابل مشاهده است.

def factorial(x):
  if x == 1:
    return 1
  else: 
    return x * factorial(x-1)
    
print(factorial(5))

خروجی:

>>>
120
>>>

نکته:مورد پایه به عنوان حالت خروجی بازگشتی عمل می کند. توابع بازگشتی می توانند بی نهایت باشند، مثل حلقه های بی نهایت. این اغلب زمانی اتفاق می افتد که شما فراموش کرده اید که پرونده پایه را اجرا کنید. در زیر یک نسخه نادرست از عملکرد فاکتوریل است. این پرونده پایه ای ندارد، و تا زمانی اجرا می شود که حافظه اجرایی سیستم پر شود و یا برنامه crash شود.

def factorial(x):
  return x * factorial(x-1)
    
print(factorial(5))

خروجی:

>>>
RuntimeError: maximum recursion depth exceeded
>>>

بازگشتی می تواند غیر مستقیم هم باشد. یک تابع می تواند یک تابع دوم را فراخوانی کند. به شکلی که این فراخوانی به صورت دو طرفه خواهد بود و تکراری. این می تواند با هر تعداد از توابع رخ می دهد. مثال:

def is_even(x):
  if x == 0:
    return True
  else:
    return is_odd(x-1)

def is_odd(x):
  return not is_even(x)


print(is_odd(17))
print(is_even(23))

خروجی:

>>>
True
False
>>>