אתר ללימוד מקיף> פרק 6 - רקורסיה

פרק 6 - רקורסיה

הנושאים בפרק זה:
6.1.     letrec
6.2.     'named let'
6.3.     איטרציות
6.4.     מיפוי פרוצדורה לרוחב רשימה

גוף הפרוצדורה יכול להכיל קריאות לפרוצדורות אחרות בין היתר לעצמה:

(define factorial (lambda (n) 
       (if (= n 0) 1 
           (* n (factorial (- n 1))))))

הפרוצדורה הרקורסיבית מחשבת עצרת של מספר (!). אם המספר הוא 0 - התשובה שתתקבל תהיה 1. לגבי כל מספר אחר n - הפרוצדורה משתמשת בעצמה לחשב עצרת של n-1, מכפילה את תוצאת הביניים ב-n, ומחזירה את המכפלה.

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

(define is-even?
   (lambda (n) 
    (if (= n 0) #t 
        (is-odd? (- n 1)))))
(define is-odd? 
   (lambda (n) 
     (if (= n 0) #f 
         (is-even? (- n 1))))

6.1 letrec

אם נרצה את הפרוצדורות לעיל כמשתנים מקומיים, נוכל לנסות להשתמש בצורת ה-let :

 (let ((local-even? (lambda (n) 
                          (if (= n 0) #t 
                              (local-odd? (- n 1)))))
       (local-odd? (lambda (n) 
                          (if (= n 0) #f 
                              (local-even? (- n 1))))))
 (list (local-even? 23) (local-odd? 23)))

כאן, הדבר לא יעבוד לגמרי כיוון שהבדיקות ?local-even ו-?local-odd בשלב האתחול לא מתייחסת למשתנים עצמם.
גם אם נשנה את let ל-*let עדיין זה לא יעבוד, היות וכל עוד ?local-even שבתוך גוף ?local-odd מתייחסת לערך הנכון של הפרוצדורה ?local-odd שבתוך גוף ?local-even עדיין מכוונת על מקום אחר.

כדי לפתור בעיה מסוג זה, Scheme מספקת את הצורה letrec:

(letrec ((local-even? (lambda (n) 
                             (if (= n 0) #t 
                                 (local-odd? (- n 1)))))
           (local-odd? (lambda (n) 
                             (if (= n 0) #f 
                           (local-even? (- n 1)))))) 
(list (local-even? 23) (local-odd? 23)))

המשתנים המוצגים ע"י letrec גלויים לא רק בתוך גוף ה-letrec, אלא גם במשך האתחולים כולם. letrec היא כאמור המתאימה ביותר עבור הגדרות רקורסיביות ופרוצדורות רקורסיביות מקומיות הדדיות.

6.2 'Named let'

פרוצדורה רקורסיבית המוגדרת באמצעות שימוש ב-letrec יכולה לתאר לולאות.
נניח כי אנו רוצים להציג ספירה לאחור החל מ-10.

(letrec ((countdown (lambda (i)
                      (if (= i 0) 'liftoff
                          (begin
                            (display i)
                            (newline)
                            (countdown (- i 1)))))))
  (countdown 10))

הפונקציה תוציא כפלט בחלון ה-console את המספרים מ-10 ועד 1 ותחזיר את התוצאה liftoff.
Scheme מציעה מגוון רחב של פונקציות let הנקראות: 'named let' כדי לכתוב סוג כזה של לולאות בצורה מתומצתת יותר:

(let countdown ((i 10))
  (if (= i 0) 'liftoff
      (begin
        (display i)
        (newline)
        (countdown (- i 1)))))

שים לב להופעת המשתנה המזהה את הלולאה מיד לאחר ה-let.
תכנית זו שקולה לתכנית הכתובה עם letrec. ניתן להתייחס ל-'named let' כאל macro (ראה פירוט נוסף בפרק 8) המרחיב את צורת ה-letrec.

6.3 איטרציות

הפונקציה countdown המוגדרת לעיל הינה פרוצדורה רקורסיבית אמיתית.
Scheme יכולה להגדיר לולאות רק בעזרת רקורסיות. אין דרך מיוחדת ליצירת לולאות או בניית איטרציות.

אעפ"כ, הלולאה המוגדרת לעיל היא לולאה אמיתית, בדיוק באותו אופן בו שפות אחרות מודיעות על הלולאות שלהן. כלומר, Scheme לוקחת על עצמה אחריות להבטיח שרקורסיות מהסוג הנראה לעיל לא ייצרו לפרוצדורה תקורת קריאות/ החזרות.

Scheme עושה זאת בעזרת תהליך הנקרא 'tail-call elimination' .אם תתבונן היטב בפרוצדורת countdown, תבחין כי כאשר מתבצעת קריאה רקורסיבית בגוף הפרוצדורה, זוהי קריאת זנב או במילים אחרות - זהו הדבר האחרון שנעשה. כל קריאה של countdown - או שהקריאה אינה לפרוצדורה עצמה, או שזו הפעולה האחרונה ממש שנעשית.
עבור מימוש Scheme , הדבר יוצר רקורסיה שאינה נבדלת מאיטרציה. אז המשך להשתמש ברקורסיה לכתוב לולאות! אל תדאג- הדבר בטוח!

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

(define list-position<
  (lambda (o l)
    (let loop ((i 0) (l l))
      (if (null? l) #f
          (if (eqv? (car l) o) i
              (loop (+ i 1) (cdr l)))))))

הפרוצדורה list-position מוצאת את האינדקס של המופע הראשון של אובייקט o ברשימה l. אם האובייקט לא נמצא ברשימה, הפרוצדורה תחזיר f#.

להלן פרוצדורת רקורסית זנב נוספת, אשר הופכת את הרשימה in place, כלומר, משנה את תוכן הרשימה הקיימת מבלי להזדקק להקצאות חדשות.

(define reverse!
  (lambda (s)
    (let loop ((s s) (r '()))
      (if (null? s) r
	  (let ((d (cdr s)))
            (set-cdr! s r)
	    (loop d s))))))

(reverse היא פרוצדורה שימושית מספיק כדי להימצא בניבי Scheme רבים, בדוגמאות ועוד).

6.4 מיפוי פרוצדורה לרוחב רשימה

ישנו סוג מיוחד של איטרציה המשלב חזרה על אותה פעולה עבור כל אלמנט ברשימה.
Scheme מציעה שתי פרוצדורות לצורך העניין: map ו-for-each .

פרוצדורת map מחילה פרוצדורה נתונה על כל אלמנט ברשימה נתונה ומחזירה את רשימת התוצאות. לדוגמא:

(map add2 '(1 2 3))
=> (3 4 5)

פרוצדורת for-each גם כן מחילה פרוצדורה נתונה על כל אלמנט ברשימה, רק שהיא מחזירה void. יישום הפרוצדורה נעשה באופן "טהור" עבור כל תופעת לוואי היכולה להיגרם.
לדוגמא:

(for-each display
  (list "one " "two " "buckle my shoe"))

כאן תופעת הלוואי היא הצגת המחרוזות (לפי סדר הופעתן) על מסך ה-console.

הפרוצדורות המופעלות ע"י map ו-for-each לא צריכות להיות פרוצדורות של ארגומנט אחד.
לדוגמא, בהינתן פרוצדורה עם n ארגומנטים - map תיקח n רשימות ותחיל את הפרוצדורה על כל סדרה של n ארגומנטים נבחרים לרוחב הרשימות. לדוגמא:

(map cons '(1 2 3) '(10 20 30))
=> ((1 . 10) (2 . 20) (3 . 30))

(map + '(1 2 3) '(10 20 30))
=> (11 22 33)