چند نکته در خصوص الگوریتم های بازگشتی

الگوریتم‌های Tail Recursion:

مفهوم Tail Recursion
الگوریتم‌های بازگشتی، تکنیکی برای حل مسائل پیچیده از طریق تجزیه آنها به زیرمسائل کوچکتر و حل آنها با استفاده از خود تابع بازگشتی هستند. یکی از انواع خاص این الگوریتم‌ها، Tail Recursion است. در tail recursion، فراخوانی بازگشتی به عنوان آخرین عملیات در تابع انجام می‌شود. به عبارت دیگر، هیچ عملیات دیگری بعد از فراخوانی بازگشتی انجام نمی‌شود. این ویژگی اجازه می‌دهد که حالت فعلی تابع دیگر نیازی به نگهداری در حافظه نداشته باشد.

به عنوان مثال، تابع بازگشتی برای پیدا کردن یک عدد در آرایه مرتب شده:

func SearchRecursive(array []int, x int) bool {
  if len(array) == 1 {
    return array[0] == x
  }

  middle := len(array) / 2
  if array[middle] == x {
    return true
  }

  if array[middle] < x && len(array) >= middle+1 {
    return SearchRecursive(array[middle:], x)
  } else {
    return SearchRecursive(array[:middle], x)
  }
}

نکته:
الگوریتم های بازگشت دمی رو ، میشه بصورت خطی نوشت.

بهینه‌سازی Tail Recursion توسط کامپایلرها
یکی از ویژگی‌های مهم بازگشت دم این است که بسیاری از کامپایلرها و مفسرهای زبان‌های برنامه‌نویسی می‌توانند این نوع بازگشت را بهینه‌سازی کنند. این بهینه‌سازی که به نام Tail Call Optimization (TCO) یا بهینه‌سازی فراخوانی دم شناخته می‌شود، به کامپایلر اجازه می‌دهد که فراخوانی‌های بازگشتی دم را به یک حلقه ساده تبدیل کند، در نتیجه نیاز به استفاده از پشته بازگشتی را حذف می‌کند.

در زبان‌های برنامه‌نویسی که از این بهینه‌سازی پشتیبانی می‌کنند، مانند Haskell، Scheme و برخی پیاده‌سازی‌های Python (مثل PyPy)، کامپایلر می‌تواند بازگشت دم را به یک حلقه for یا while تبدیل کند:

def factorial(n):
    acc = 1
    while n > 0:
        acc *= n
        n -= 1
    return acc

این تبدیل باعث می‌شود که عملکرد و بهره‌وری برنامه بهبود یابد، زیرا دیگر نیازی به افزایش عمق پشته بازگشتی برای هر فراخوانی وجود ندارد.

محدودیت‌های Recursion Stack
در اکثر زبان‌های برنامه‌نویسی، هر بار که یک تابع بازگشتی فراخوانی می‌شود، یک فریم جدید به پشته بازگشتی اضافه می‌شود. پشته بازگشتی یا recursion stack مکانی است که اطلاعات مربوط به هر فراخوانی، شامل پارامترها، متغیرهای محلی و آدرس بازگشت، ذخیره می‌شود.

این پشته محدودیت‌های خاص خود را دارد:
1. محدودیت حافظه: هر پشته بازگشتی مقدار مشخصی از حافظه را مصرف می‌کند. در صورتی که عمق بازگشتی زیاد باشد، ممکن است برنامه با خطای Stack Overflow مواجه شود.
2. کاهش کارایی: هر فراخوانی بازگشتی نیاز به زمان اضافی برای مدیریت فریم‌های پشته دارد که می‌تواند منجر به کاهش کارایی شود.
3. پیچیدگی کد: مدیریت دستی بازگشت‌ها و پارامترها می‌تواند کد را پیچیده‌تر و مشکل‌تر برای فهم کند.

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

#recursion

@Syntax_fa