איך לתרגל שאלות רקורסיה בשפות תכנות?

באתר prepd תמצאו שאלות רקורסיה בשפות תכנות ממבחנים אמיתיים של האוניברסיטה הפתוחה. השאלות ממוינות לפי רמת קושי.

כמה שאלות רקורסיה יש בשפות תכנות?

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

מה חשוב לדעת על רקורסיה לקראת מבחן בשפות תכנות?

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

שפות תכנות - רקורסיה

תכנות פונקציונלי, מודל הסביבה, זרמים, תכנות לוגי ומערכות טיפוסים

סטטיסטיקות מבחנים

תתי-נושאים של תכנות פונקציונלי

רמת קושי:

שאלה זו עוסקת בשדרוג של שפת "ויהיי" (שפת LET) המתוארת בספר הלימוד בפרק 3 בעמודים 60-74.

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

להלן הדקדוק של לולאת do:

Expression ::= do (
                { < Identifier  Expression  Expression > }+
                { [ Expression  Expression ] }+
               )

מבנה הנתונים המייצג את הביטוי:

do-exp (ids inits steps bools results)

הסבר לדקדוק:

ביטוי do-exp מגדיר כמות שרירותית (לפחות אחד) של משתנים מספריים (ids), למשתנים יש ערכים התחלתיים הנתונים ע"י הביטויים inits, ובכל מחזור לולאה גדלים הצעדים הנתונים ע"י ביטויים steps.

כמו כן, ללולאה כמות שרירותית (לפחות אחד) של ביטויים בוליאניים (bools), בכל מחזור לולאה נבדקים הביטויים הבוליאניים, והראשון מביניהם שערכו אמת, יגרום ללולאה להיעצר ולהחזיר את ערכו המתאים מתוך ביטוי results המתאים לביטוי הבוליאני שנמצא אמת.

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

הבהרות:

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

דוגמה 1:

> (run "do(
          <a 0 4>
          <b 7 -(a,2)>
          <c -(b,1)  -(a,b)>
          [zero? (b)     -(a,c)]
          [zero? (-(c,-2))  -(a,5)]
        )
")
(num-val 3)
>

בדוגמה זו, התוכנית מורכבת מלולאת do המגדירה 3 משתנים a,b,c. בתחילה a שווה לאפס, b שווה ל-7, c שווה ל-1 (6- פחות 1).

כעת נבדקים התנאים הבוליאניים לפי סדר הופעתם. התנאי הבוליאני הראשון בודק האם ערכו של b הוא 0, תנאי זה אינו מתקיים כרגע. התנאי הבוליאני השני בודק האם ערכו של c הוא 2-, גם הוא לא מתקיים כרגע.

מאחר ואף תנאי בוליאני לא התקיים, הלולאה ממשיכה למחזור הבא שלה, שבו היא תעבוד עם משתנים a,b,c שערכם הוא כעת:

a שווה ל-4, כי היה לו 0 והתווסף לו 4
b שווה ל-5, כי היה לו 7 והוא גדל ב-2 (a-2), a במצבו הנוכחי (לפני שקודם) היה 0 ולכן a-2 זה 2-
ולכן b קטן ב-2 מ-7 לכן 5-
c שווה ל-1, כי היה לו 6 והתווסף לו a-b (לפני שקודמו) היה 0 ו-7- בהתאמה ולכן c קטן ב-7 ונהיה 1-

כעת נבדקים שוב התנאים הבוליאניים, וניתן לראות ששוב אף אחד מהם אינו נכון, ולכן הלולאה ממשיכה למחזור הבא שלה, עם משתנים a,b,c שערכם הוא:

a שווה ל-8, כי היה לו 4 והתווסף לו 4
b שווה ל-7, כי היה לו 5, והוא גדל ב-2 (a-2) שזה 2
c שווה ל-2, כי היה לו 1- והוא גדל ב-(a-b) שזה 1-

וכעת שוב נבדקים התנאים הבוליאניים (לפי הסדר בו הם כתובים) וכעת התנאי הבוליאני השני מתקיים! ולכן הלולאה נעצרת ומוחזר ערכו של הביטוי הכתוב לצד התנאי הבוליאני שהיה אמת, שבמקרה זה הביטוי הוא a-5 שערכו הנוכחי הוא 8-5=3 ולכן תוצאת התוכנית היא 3.

דוגמה 2:

> (run "do(
          [zero? (b)     -(a,c)]
          [zero? (-(c,-2))  -(a,5)]
        )
")
 interp.scm:72:15: do-exp: do loop with no variables are not allowed
>

בדוגמה זו יש לולאת do ללא הגדרת משתנים, על פי הדקדוק הנתון בשאלה נדרש לפחות משתנה אחד ולכן התקבלה הודעת שגיאה מתאימה.

דוגמה 3:

> (run "do(
          <a 0 4>
          <b 7 -(a,2)>
          <c -(b,1)  -(a,b)>
        )
")
 interp.scm:74:19: do-exp: do loop with no booleans are not allowed
>

בדוגמה זו יש לולאת do ללא הגדרת תנאים בוליאניים, על פי הדקדוק הנתון בשאלה נדרש לפחות תנאי בוליאני אחד ולכן התקבלה הודעת שגיאה מתאימה.

ממשו והטמיעו את השינויים הדרושים כפי שהוגדרו והודגמו לעיל בתוך שפת "ויהיי" (שפת LET). בתשובתכם, הקפידו להסביר היכן בדיוק נדרשים שינויים ותוספות בקבצי המפרש, ומהם השינויים והתוספות.

הנחיות כלליות לפתרון:
1. הקפידו על כתב ברור, ועל קוד מבני ומסודר.
2. הקפידו על פתיחת וסגירת סוגריים במקומות הנכונים.
3. הפתרון אמור לשמור על הגדרות השפה המקוריות (פרט לשינויי כזה נדרש שינויי כזה במפרש בשאלה).
4. על מנת לפשט קוד ארוך, כדאי ורצוי להיעזר בכתיבת פרוצדורות עזר (מחוץ ל-value-of או כאלה המוטמעות בתוכו).
5. בפתרונכם, הקפידו על אבחנה וכן שימוש נכון בין ביטוי (expression) לבין תוצאת חישוב ביטוי (expval) לבין identifier.
6. ניקוד יורד על אי ניתוח ומימוש נכון של הדקדוק הנתון בשאלה, כלומר יש להפקיד על זיהוי וטיפול נכון ב-terminals, non-terminals ופעולות של סגור ()* או { }+).

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד ב · 2023 · סמסטר ב

★★★★★

מפרשיםSchemedefineתכנות פונקציונלירקורסיה

שאלה א (7 נקודות)

להלן מופיעים ההגדרות של scanner ו-parser של שפת "יוטורג" עיסקו להשלמת הטעם הראשוני של שפה.

ה-scanner:

(define the-lexical-spec

^{'} ((whitespace (whitespace) skip)

(\text{comment } (\text{"\#" (arbno (\text{not } \#\backslash\text{newline}))) \text{ skip})

(\text{identifier}(\text{letter (arbno (or letter digit } \text{\"_\" \"-\" \"?\")))

symbol)

(\text{number (digit (arbno digit))) number)

(\text{number (\"-\" digit (arbno digit))) number)

))

ה-parser:

(define the-grammar

^{'} ((program (expression) a-program)

(expression (number) const-exp)

(\text{expression (\"-(\" expression \",\" expression \")\"))

diff-exp)

(expression (\overset{z}{¨} ero? ¨ \ddot{(} ¨ expression \ddot{)} \ddot{)}) zero?-exp)

(expression (\ddot{i} f ¨ expression \ddot{t} hen ¨ expression \overset{e}{¨} lse ¨ expression))

if-exp)

(expression (identifier) var-exp)

(expression (\ddot{l} et ¨ identifier \overset{=}{¨} ¨ expression \ddot{i} n ¨ expression))

let-exp)

(expression (\overset{p}{¨} roc ¨ \ddot{(} ¨ identifier \ddot{)} \ddot{)} expression)

proc-exp)

(expression (\ddot{(} ¨ expression expression \ddot{)} \ddot{)}) call-exp)

(expression

את התשובה יש לכתוב במחברת הבחינה

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמבחן 2017 סמסטר ב · 2017 · סמסטר ב

★★★★★

מפרשיםevalמודל הסביבהרקורסיהletSchemeסגורים

שאלות רקורסיה בשפות תכנות עם פתרונות

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