פונקציה רקורסיבית
לעיתים אפשר להימנע מלהשתמש בפונקציה רקורסיבית, ואפשר לעשות את העבודה בדרכים מעט ארוכות יותר, אבל קריאות ומובנות יותר. מצד שני, אין דבר שעושה רושם גדול יותר על המראיינים שלכם בעתיד או בכלל מאשר לנסח פונקציה רקורסיבית קצרה שעושה את העבודה ומדהימה את הלקוח. חוץ מזה אנחנו בעניין פיתוח חשיבה אנליטית, וגם באנו ליהנות.
קודם נגיד את זה - מדובר בפונקציה שמחזירה מלבד ערך כלשהו גם את עצמה באופן מעגלי עד לסיום עבודתה. לנוכח מורכבות העניין, חבל להכביר מילים ונתאר בדוגמא.
פיבונאצ'י - fibonacci בפונקציה רקורסיבית
הדוגמא הראשונה תהיה אותה סדרת פיבונאצ'י שכתבנו לגביה תוכנית בתרגיל למעלה, (0,1,1,2,3,5,8…) שכל איבר שווה לסכום שני האיברים שלפניו בסדרה. אלא שהפעם נבנה את הדברים מעט אחרת, באמצעות פונקציה רקורסיבית שמחזירה את האיבר ה- n (למשל אם n==7 התוכנית תחזיר את המספר 8 שהוא האיבר השביעי). כמובן ש n לא יכול להיות 0 בתוכנית הזאת, אחרת תוחזר שגיאה.
def fib(n):
if n==1:
return 0
elif n==2:
return 1
else:
return fib(n-1)+fib(n-2)
for i in range(1,11): print (fib(i))
>>>
0
1
1
2
3
5
8
13
21
34
ניתן לראות בתוכנית המגדירה את הפונקציה fib שנעשה שימוש בפונקציה fib, גם בתוך הגדרת הפונקציה עצמה ! (מסתבר שאפשר לעשות את זה).
אם n שווה ל- 1 מדובר באיבר הראשון בסדרה ולכן התוכנית מחזירה 0 ואינה ממשיכה לרוץ משום ששרשרת התנאים (או בלוק התנאים) if,elif,else היא אלטרנטיבית, כלומר אם מתקיים תנאי באחד מהחלקים בשרשרת, לא ממשיכים לתנאים הבאים בשרשרת ובמקרה הזה הלולאה מסתיימת.
כנ"ל אם n שווה ל- 2 אנו נלכדים בתנאי השני elif והתוכנית מחזירה את המספר 1 שהוא האיבר השני בסדרה שלנו ובכך מסתיימת הלולאה ואנו יודעים שהאיבר השני בסדרת פיבונאצ'י שלנו הוא 1.
אם אנו מחפשים את האיבר השלישי (n==3) בסדרה, אנו לא נלכדים בהתחלה בתנאי הראשון והשני אלא בתנאי הכתוב ב- else - והתוכנית מחזירה את הערך (fib(n-1)+fib(n-2 כלומר (fib(2)+fib(1 ולכן מריצה שוב את הפונקציה fib (כמו בלולאות האחרות שלמדנו עליהן) על המספרים האלה. (fib(2 ילכד בתנאי השני ויחזיר את הערך 1 ו- (fib(1 נלכד ב- if הראשון ומחזיר את הערך 0 ולכן התוכנית מחזירה את הסכום שלהם (0+1) השווה ל- 1. לכן האיבר השלישי בסדרת פיבונאצ'י שלנו הוא 1.
אם נחפש את האיבר הרביעי בסדרה (n==4) הלולאה שלנו תרוץ כמה פעמים – פעם ראשונה תחזיר (fib(3)+fib(2 לגבי (fib(2 אנו יודעים שהערך הוא 1 לגבי (fib(3 אנו יודעים שהתוכנית רצה כפי שהראנו בתוכנית הקודמת כשחיפשנו את האיבר השלישי ובסוף היא מחזירה את הערך 1 – כך שסכום האיברים בסדרת פיבונאצ'י (השני והשלישי) הוא 1+1 וזה שווה ל- 2. כך שהאיבר הרביעי בסדרה הוא 2.
וכך הלאה התוכנית תרוץ מספר סיבובים גדול יותר, ככל שמיקום האיבר בסדרת פיבונאצ'י הוא גדול יותר (כל פעם תחשב את סכום שני האיברים הקודמים) ולבסוף תחזיר את ערך סכום שני האבירים שלפני ה n שאותו ביקשנו לבדוק.
לבסוף – כדי לקבל סדרה של עשרת מספרי הפיבונאצ'י מהראשון (שהוא 1 ולא 0) ועד לעשירי (כתבנו 11 כי האחרון אינו כלול) אנו מריצים לולאת for בשילוב עם פקודת range שתדפיס את ערך הפיבונאצ'י מהאיבר הראשון עד העשירי (כולל העשירי).
נעשה עוד אחד – הפעם כזה שמחשב את הפעולה המתמטית עצרת ! –
חחח זה לא מסוג הדברים שניתן להבין בקריאה סתמית בטח לא בקריאה של פעם אחת, תנסו לעקוב אחר השלבים לאט לאט.
חישוב עצרת ! בפונקציה רקורסיבית
עצרת (factorial בלעז) של מספר כלשהו היא מכפלת כל המספרים הקודמים לו (לא כולל 0 – אחרת זה תמיד 0) במספר עליו מבצעים את הפעולה. למשל !5==1*2*3*4*5 (ישים לב הקורא שאני משתמש ב- == כמו בפייתון ולא ב - = אחד כמו המורה שרה ביסודי).
def fact(n):
if n==1:
return 1
else:
return n*fact(n-1)
print(fact(4))
>>>
24
שוב הגדרנו פונקציה בשם fact היודעת לחשב עצרת עבור כל מספר n. כאשר בתוך הגדרת הפונקציה, עושים שימוש בפונקציה עצמה. כדי לחשב את תוצאת העצרת של המספר 4, נעקוב אחר הלולאה שמבצעת התוכנית –
התוכנית בהתחלה לא נלכדת בתנאי הראשון של if n==1 ולכן מחזירה (4*fact(3. את (fact (3 היא מחזירה ללולאה והיא מקבלת (3*fact(2. את fact(2) היא מחזירה ללולאה ומקבלת (2*fact(1) . fact(1) מחזיר את הערך 1 ועכשיו עושים את כל הדרך חזרה – ומקבלים ש (fact(2 שווה 2. ו-(fact(3 שווה (3*fact(2 ולכן שווה ל- 6 ולכן (fact(4 שווה ל- 4*6 שהם 24.
ננסה לסדר את אופן החישוב שמבצעת התוכנית בטבלה:
