רקורסיה ומחסנית הקריאות - כיצד פונקציה קוראת לעצמה

רקורסיה היא כאשר פונקציה קוראת לעצמה כחלק מחישובה. זוהי כלי עוצמתי שמאפשר לפתור בעיות מורכבות בקוד קומפקטי - ועומד בבסיסם של מיון מיזוג, Quick Sort, DFS, ועצי BST.

שני מרכיבים הכרחיים

• מקרה בסיס (Base Case) - התנאי שמפסיק את הרקורסיה. בלעדיו יש הצפת מחסנית (Stack Overflow)
• מקרה רקורסיבי - קריאה לאותה פונקציה עם קלט קטן יותר שמתקרב למקרה הבסיס

דוגמה - עצרת (Factorial)

function factorial(n) {
  if (n <= 1) return 1;          // מקרה בסיס
  return n * factorial(n - 1);   // מקרה רקורסיבי
}

// factorial(4)
// = 4 * factorial(3)
// = 4 * 3 * factorial(2)
// = 4 * 3 * 2 * factorial(1)
// = 4 * 3 * 2 * 1 = 24

מחסנית הקריאות (Call Stack)

כל קריאה רקורסיבית דוחפת מסגרת (frame) למחסנית הקריאות - הכוללת את המשתנים המקומיים ונקודת החזרה. כשמגיעים למקרה הבסיס, המסגרות נפרקות בחזרה בסדר הפוך.

Tail Recursion

אם הקריאה הרקורסיבית היא הפעולה האחרונה בפונקציה (ללא חישוב אחרי החזרה), המהדר יכול לבצע 'אופטימיזציית זנב' ולהמיר לולאה - חוסך זיכרון מחסנית. זה נפוץ ב-Haskell ו-Scala, ונתמך חלקית ב-JavaScript בסביבות מסוימות.

רקורסיה מול איטרציה