כשלומדים רקורסיה לא תמיד ברור למה צריך את המבנה הזה, הרבה פעמים בגלל שאנחנו מנסים לפתור בצורה רקורסיבית שאלות שלא הכי מתאימות לחשיבה הרקורסיבית. המקרה של יום 9 ב Advent Of Code השנה המחיש איך שאלות מסוימות מזמינות את הפיתרון הרקורסיבי, ונפתרות בקלות בזכותו.

1. התרגיל

המשימה שלנו היא לחשב את האיבר הבא בסידרה דרך חישוב סדרת ההפרשים שלה. ניקח לדוגמה את סידרת המספרים:

1   3   6  10  15  21

אז אפשר לרשום את ההפרש בין כל שני מספרים ולקבל את הסידרה:

2   3   4   5   6

ואפשר להמשיך ולרשום את ההפרש בין כל מספר בסידרת ההפרשים כדי לקבל את הסידרה:

1   1   1   1

ואז להמשיך עוד שלב כדי לקבל:

0   0   0

כשמגיעים לסידרת האפסים נוסיף אפס אחד, ואז נשתמש בו כדי לחשב את האיבר הבא בסידרת ה-1-ים (הוא יהיה 1), ואז נשתמש בו כדי לגלות את האיבר הבא בסידרה השנייה (הוא יהיה 7) ובעזרתו מוצאים את המספר האחרון בסידרה שממנה התחלנו - הוא יהיה 28.

2. פיתרון בסקאלה

נכתוב פונקציה בסקאלה שתחשב את המספר הבא בסידרה. לפונקציה יש בסך הכל שתי אפשרויות:

1. או שהיא מקבלת סידרה שכולה אפסים, ואז היא מוסיפה לה עוד 0.

2. או שהיא מקבלת סידרה אחרת, ואז היא תחבר את האיבר האחרון בסידרה עם האיבר האחרון בסידרה שתתקבל מהפעלת אותה פונקציה על סידרת ההפרשים.

את סידרת ההפרשים מחשבים בסקאלה עם השורה הבאה:

val diffSeries = known.zip(known.tail).map {(i, j) => j - i }

ולכן הפונקציה כולה תהיה:

  def addNextValue(known: List[Long]): List[Long] =
    known match
      case _ if known.forall(l => l == 0) => known :+ 0
      case _ =>
        val diffSeries = known.zip(known.tail).map {(i, j) => j - i }
        known :+ known.last + addNextValue(diffSeries).last