תרגילים ללימוד בשפת C

רקורסיה

רמה קלה

תרגיל 1

יש לכתוב פונקציה רקורסיבית אשר תשרטט משולש מכוכביות. הפונקציה תקבל את גודל המשולש כפרמטר ובכל קריאה תשרטט שורה מתוך משולש. דוגמה למשולש בגודל 4:

*

**

***

****

תרגיל 2

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

תרגיל 3

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

תרגיל 4

כתוב פונקציה רקורסיבית המקבלת מספר n, ומחזירה את המספר ה-n-י בסידרת פיבונצי.

תרגיל 5

כתוב פונקציה רקורסיבית המקבלת מערך ומחזירה 1 אם כל איברי המערך חיוביים או 0 אחרת.

תרגיל 6

כתוב פונקציה רקורסיבית המקבלת מערך ומדפיסה את כל איבריו מהסוף להתחלה.

תרגיל 7

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

תרגיל 8

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

רמה בינונית

תרגיל 1

הספרייה הסטנדרטית string.h  מספקת פונקציות לטיפול במחרוזות.

יש לממש בעזרת רקורסיה את הפונקציות הבאות המקבילות לפונקציות מהספרייה :srting.h

unsigned strlen_rec (char *str);

הפונקציה מחזירה את מספר התווים במחרוזת.

char* strcpy_rec(char *str1, char *str2);

הפונקציה מעתיקה את המחרוזת str2 למחרוזת str1 ומחזירה את כתובת המחרוזת str1

int strcmp_rec(char *str1, char *str2);

הפונקציה משווה בין המחרוזת str1 למחרוזת str2 ומחזירה:

0 אם המחרוזות זהות, או  str1[i]-str2[i]כאשר i האינדקס של התו השונה הראשון.

char* strcat_rec(char *str1, char *str2);

הפונקציה משרשרת את המחרוזת str2 לסוף המחרוזת str1 ומחזירה את כתובת המחרוזת str1.

תרגיל 2

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

תרגיל 3

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

ה-ASCII שלהם קטן מזה של האות האחרונה במחרוזת.

תרגיל 4

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

תרגיל 5

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

תרגיל 6

נתונה הסידרה הבאה:  0,1,1,2,5,29,…. בסדרה זו האיבר הראשון 0, האיבר השני 1, וכל איבר אחר בסדרה הוא סכום ריבועי שני האיברים שלפניו.

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

רמה קשה

תרגיל 1

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

דוגמא: עבור המחרוזת cfgrti  תודפסנה האותיות gf.

דרישות:

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

תרגיל 2

a הוא מערך שלמים באורך n. ידוע ש- n  אי-זוגי.

א. השלם את הקוד הרקורסיבי הבא כך שידפיס את אברי a בסדר הבא משמאל לימין:

a[0],  a[n-1],  a[1],  a[n-2],  ...,  a[(n-1)/2]

    בכל מקום חסר יש לכתוב פסוק פשוט (simple statement) אחד בלבד.

     ב. השלם את הקוד הרקורסיבי הבא כך שידפיס את אברי a בסדר הבא משמאל לימין:

a[(n-1)/2],  a[(n-1)/2 - 1],  a[(n-1)/2 + 1],  ...,  a[0],  a[n-1]

תרגיל 3

כתוב פונקציה רקורסיבית, אשר מקבלת מספר טבעי N, ותדפיס את N מספרים הראשונים של הסדרה הבאה: 1, 2, 4, 7, 11, 16, 22, ….