שפת C - רקורסיה - תרגילים וכללים

רקורסיה - שיטה לבנייה נכונה

פתרונות מהשיעור הקודם:

תשובה 1: (לא רשמי)

#include <stdio.h>
 
int  f1(int x,int y) {
 if (x<y||(x==y&&x%2==1))   // הפונקציה מחזירה את סכום המספרים הזוגיים בין שני מספרים כשהשמאלי גדול או שווה לימיני
  return 0;
 if (y%2==1) 
  y++;
 return 1 + f1(x, y+2);
 }
 
 void main() {
  int x,y;
  printf("Enter 2 numbers: ");
  scanf("%d %d",&x,&y);
  printf("Zugi: %d \n",f1(x,y));
 }

תשובה 2: (לא רשמי)

#include <stdio.h>
    
   int Count (int *A) {  // הפונקציה מחזירה את סכום איברי מערך שהאיבר האחרון בו הוא -1
    if (*A==-1)
     return -1;
    return *A + Count(A + 1);
   }
 
  void main() {
   int A[5] = {1,2,100,5,-1};
   printf ("Count:  %d",Count(A));
  }

תשובה 3: (לא רשמי)

#include <stdio.h>
 
  int f12 (int a, int b) { // מקבלת 2 מספרים ומחזירה את המכנה המשותף הגדול ביותר בינהם - שימוש באלגוריתם אוקלידס
   int n;
   if(a<b) {
    n = a;
    a = b;
    b = n;
   }
   if (a % b==0)
    return b;
   return f12(a-b,b);
  }
 
    void main() {
  int a ,b;
  printf("enter 2 numbers: ");
  scanf("%d %d", &a , &b);
  printf("%d \n" ,f12(a,b));
 }

תשובה 4: (לא רשמי)

#include <stdio.h>
 
void K300(int x) { // הפונקציה מדפיסה סדרה חשבונית שכל זוגי מתחלק ל 2 וכל אי זוגי מוכפל ב 3 פלוס 1
 if (x==1){
  printf("1\n");
  return ;
}
 printf("%d ",x);
if(x%2==0)
 x = x/2;
else 
 x = x*3 +1;
K300(x);
}
 
void main() {
  int x;
  printf("Enter number: ");
  scanf("%d",&x);
  K300(x);
 }

תשובה 5: (רשמי) (רצוי לעיין מהוא אופן הפעולה הרצוי של strcpy)

דרך א:

void strcpy(char *s1, char *s2) { 
 if(*s2 == NULL) {
  *s1 = NULL;
  return;
 }
 *s1 = *s2;
 strcpy(s1+1, s2+1);
}

דרך ב:

void strcpy(char *s1, char *s2) { 
 *s1 = *s2;
 if(*s2 == NULL)
  return;
 
 strcpy(s1+1, s2+1);
}

עד כאן.

ננסח את הכללים לבניית פונקציה רקורסיבית:

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

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

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

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

דוגמאות:

עבור n ידפיס:

1 2 3 4 5 ... n

void f(int n){
 if (n==0)  //  כלל ראשון: תנאי יציאה עבור המקרה הפשוט ביותר
  return;
 f (n-1);  // n-1 כלל שני: נאמין שהפונקציה שלנו מסוגלת לעבוד, ושהשורה הזאת מדפיסה כבר את כל המספרים עד 
 printf("%d",n);  // n נותר רק להדפיס את האיבר האחרון n-1 כלל שלשי: אחרי שהאמנו שהשורה הקודמת הדפיסה הכל עד 
}

עבור n יחזיר סכום:

1+2+3+ ... n

int f(int n){
 if (n==0)  // כלל ראשון: תנאי יציאה עבור המקרה הפשוט ביותר
  return 0;
 return f(n-1)+n; // n נותר רק להוסיף לסכום את האיבר האחרון n-1 החזירה את סכום הכל עד f(n-1) כלל שני ושלשי: אחרי שהאמנו ש
}

הפונקציה הבאה מקבלת מצביע מערך ואת אורכו ומחזירה ממוצע האיברים:

double AVG(int A[], int n){
 if (n==1)  // כלל ראשון: תנאי יציאה עבור המקרה הפשוט ביותר
  return A[0];
 
  // n-1 החזירה את ממוצע הכל עד AVG(A,n-1) כלל שני ושלשי: אחרי שנאמין ש
                // n-1 כדי למצוא את סכום כל האיברים עד n-1 נכפיל חזרה ב
                          //  n ונחלק ב  A[n-1] נוסיף את האיבר האחרון
 return (AVG(A,n-1)*(n-1) + A[n-1])/n ;

}

אחרי שהבנתם נסו משהו קשה באמת:

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

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

לדוגמה:

עבור 4 (כלומר 4 טבעות)

הפונקציה תדפיס:

Move ring from 1 to 2

Move ring from 1 to 3

Move ring from 2 to 3

Move ring from 1 to 2

Move ring from 3 to 1

Move ring from 3 to 2

Move ring from 1 to 2

Move ring from 1 to 3

Move ring from 2 to 3

Move ring from 2 to 1

Move ring from 3 to 1

Move ring from 2 to 3

Move ring from 1 to 2

Move ring from 1 to 3

Move ring from 2 to 3

והמשמעות של זה היא:

כדאי לתת לפונקציה גם את הערך אסקי של התוים A B ו C באופן הבא:

void hanoi(char x, char y, char z, int n){

[לקריאה נוספת ומקור התמונה]

[סרטון הדגמה עם 8 טבעות]

אחרי שניסיתם כמה ימים...

הנה תוכנית נכונה

בהצלחה.