|
|
עמוד:284
7 . 8 פונקציה רקורסיבית פונקציה רקורסיבית היא פונקציה שבמהלכה הפונקציה מזמנת את עצמה . הרקורסיה היא כלי נוח ומתוחכם לפיתוח אלגוריתמים לפתרון בעיות , ובמקרים מסוימים היא מפשטת את תהליך הפתרון . בסעיף זה נסביר תחילה מהו חישוב רקורסיבי ונציג את המבנה של האלגוריתם הרקורסיבי ; בהמשך נתאר כיצד המעבד משתמש במחסנית לביצוע תכנית שמכילה פונקציה רקורסיבית . דוגמה 7 . 10 נתאר חישוב רקורסיבי של פונקציה המחשבת עצרת של מספר חיובי ושלם . עצרת של המספר n הוא מכפלת כל המספרים השלמים מ1- עד מ , כאשר 0 עצרת מוגדר כ . 1- משתמשים בסימן ! כדי לציין עצרת , לדוגמה , שתיים עצרת נכתב , 2 ! ובאופן כללי , עבור n רושמים . n ! נראה שני חישובים לדוגמה : 3 עצרת מחושב כ- 3 ! = 3-2-1 7 עצרת מחושב כ 7 ! = 7-6-5-4-3-2-1- וכדומה . אלגוריתם איטראטיבי הוא אלגוריתם המבצע חזרה מפורשת של קטע מסוים בו , כמה פעמים . האלגוריתם לחישוב 11 עצרת עבור n > 0 הוא פשוט ומוכר ( המילה "עצרת" באנגלית היא : ( "factorial" factorial = 1 לכל n-o * עד 1 בצע : x = x- 1 factorial = factorial x אבל אפשר לחשב עצרת של מספר גם בעזרת תהליך רקורסיבי . נבחן כמה מקרים פרטיים וננסה למצוא כלל לחישוב . n ! נתחיל ברישום מפורש של נוסחת החישוב עבור ת-ים שונים ) במהרה נגלה כי יש קשר בין חישוב ! וז לחישוב מקרה פשוט יותר שהוא -1 )! ו ? . ( 1
|
|