תרגיל – בניית משולש פסקל באמצעות פונקציה רקורסיבית

תרגיל – בניית משולש פסקל באמצעות פונקציה רקורסיבית

משולש פסקל הוא מעין פירמידה שמתחילה במספר 1 וככל שיורדים בפירמידה, כל מספר שווה לסכום שני המספרים שמעליו – נציג את ארבע הקומות העליונות של הפירמידה (אפשר להמשיך בלי סוף במורד הפירמידה):

1

1 1

1 2 1

1 3 3 1

רמז – פסקל מזכיר במבנה שלו את סיפור פיבונאצ'י רק במקום לחשב שני מספרים קודמים בסדרה אנו מחפשים סכום של שני מספרים מסוימים בשורה למעלה.

רמז 2 – אפשר לכתוב תוכנית שתייצר רשימה עבור כל שורה במשולש פסקל, כך למשל שורה מס' 1 תכיל איבר אחד [1] השורה השנייה שני איברים [1,1] השורה השלישית , שלושה [1,2,1] וכו'.

אחד הפתרונות -

def pas(n):

if n == 1:

return [1]

else:

row = [1]

uprow = pas(n-1)

for i in range(len(uprow)-1):

row.append(uprow[i] + uprow[i+1])

row += [1]

return row

for i in range (1,8):

print (pas(i))

>>>

[1]

[1, 1]

[1, 2, 1]

[1, 3, 3, 1]

[1, 4, 6, 4, 1]

[1, 5, 10, 10, 5, 1]

[1, 6, 15, 20, 15, 6, 1]

הסבר – בנינו פונקציה רקורסיבית בשם pas המייצרת את איברי השורה הרלבנטית (n) במשולש פסקל. את השורה הראשונה אנו מייצרים באופן "ידני" באמצעות יצירת רשימה בעלת איבר אחד [1] כאשר n שווה 1.

אחרת, כאשר n גדול מ- 1 אנו מייצרים רשימה חדשה בשם row (ואנו כבר יודעים שהאיבר הראשון בה יהיה 1, כי כך מתחילות כל השורות במשולש פסקל). כמו כן, אנו מייצרים משתנה נוסף בשם uprow שגם הוא יהיה רשימה בסופו של דבר, אליו נכניס שוב פעם את הפונקציה pas הפעם מופעלת על השורה הקודמת הגבוהה יותר בפירמידה (n-1) .

כעת מוסיפים לשורה row את סכומי המספרים שמעל וסוגרים את השורה באמצעות הוספת המספר 1, הסוגר כל שורה במשולש פסקל.

כאשר uprow מפסיק להיות נוסחה והופך לרשימה [1] יש לנו ב- row את הערך [1] , בשלב זה for i in range(len(uprow)-1) לא יעשה שום דבר כי האורך של uprow הוא 1 אבל האורך המתקבל מ- len(uprow)-1 הוא ==1-1, כלומר 0 ולכן לולאת ה for הזאת לא תרוץ כלל (for i in range(0 עושה משהו 0 פעמים, אבל אנחנו נעבור לשורה הבאה בקוד [row += [1 אשר מוסיפה לרשימה row את המספר 1 והוא הופך ל- [1,1] .

נדגים בטבלה את התהליך הרקורסיבי של יצירת השורה החמישית n==5 במשולש פסקל –

כפי שניתן לראות, פעולת הרקורסיה אינה תמיד קלה להבנה, ויתכן שידרש לאנשים שלא נתקלו בתופעה קודם לכן, יותר זמן. לפעמים היא מיועדת, שלא בצדק, לשמור על מקום העבודה של מי שכותב את הקוד, תחת ההנחה שכשאף אחד חוץ ממך לא מבין מה כתוב, תמיד יצטרכו אותך. אני לא מאמין בזה. אני מאמין בקוד קריא גם אם הוא מעט ארוך יותר, אבל לצורך פיתוח האינטלקט אין טוב מזה.