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

1. תרגיל: פתרון ביטוי חשבוני

ביטוי חשבוני הוא מבנה נתונים רקורסיבי שיכול לכלול תתי ביטויים, כך את הביטוי הבא:

1 + 2 * 2 + 3 * 2

אנו קוראים כסכום של 3 ביטויים, הראשון הוא המספר 1, השני הוא הביטוי 2 * 2 והשלישי הוא הביטוי 3 * 2.

אפשר לייצר ביטוי חשבוני בשפת פייתון באמצעות המחלקה הבאה:

import numbers
import operator

class Expression:
    def __init__(self, op, x, y):
        self.op = op
        self.x  = x
        self.y  = y

e = Expression(
    operator.add,
    1,
    Expression(
        operator.add,
        Expression(operator.mul, 2, 2),
        Expression(operator.mul, 3, 2)
        )
    )

כל ביטוי מתיחס לביטויים אחרים ולכן במבנה הנתונים Expression הערכים x ו-y עשויים להיות מספרים, אבל גם עשויים להיות ביטויים אחרים.

כתבו פונקציה val המחשבת ערך ביטוי, כך שהקוד הבא ידפיס 11:

e = Expression(
    operator.add,
    1,
    Expression(
        operator.add,
        Expression(operator.mul, 2, 2),
        Expression(operator.mul, 3, 2)
        )
    )

print(val(e))

2. תרגיל: זיהוי אזורים במטריצה

נתון הקלט הבא המתאר לוח משחק (אולי שולה המוקשים. אף פעם לא הצלחתי להבין את החוקים של המשחק הזה):

...##...
#......#
....####
........
.......#

 

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

...aa...
b......c
....cccc
dd......
.......e

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

3. תרגיל: הדפסת מכפלה קרטזית של מספר מערכים

בהיתנן רשימה כלשהי של מערכים בפייתון:

x = ['a', 'b']
y = ['x', 'y']
z = ['1', '2']

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

print(prod(x, y, z))

ידפיס את התוצאה:

['ax1', 'ax2', 'ay1', 'ay2', 'bx1', 'bx2', 'by1', 'by2']

הפונקציה יכולה לקבל כל מספר של מערכים כקלט.