שפת C - רקורסיה

רקורסיה - recursion

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

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

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

לדוגמה נתבונן בפונקציה רקורסיבית שמחזירה סכום המספרים מ0 ועד למספר שהיא מקבלת.
עבור 5 הפונקציה תחזיר סכום: 1+2+3+4+5

#include<stdio.h>
 
int f(int n){
 if(n==0)
  return 0;
 return n+f(n-1);
}
 
void main(){
 int n;
 printf("Enter number: ");
 scanf("%d",&n);
 printf("%d\n",f(n));
 
}

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

#include<stdio.h>
 
void f(int n){
 if (n==0)
  return;
 f(n-1);
 printf("%d",n);
}
 
void main(){
 f(5);
}

תשובה בלבן: 12345

................................

נסו לכתוב את הפונקציה strlen!

(מקבלת שם של מערך מסוג מחרוזת (=מצביע) ומחזירה את אורך המחרוזת)

פתרון:

#include<stdio.h>
 
int strlen(char *s){
 if(*s == NULL)
  return 0;
 return 1 + strlen(s+1);
}
 
void main(){
 char str[] = "Barkai Class";
 printf("%d\n",strlen(str));
}

שימו לב לחשיבות תנאי היציאה ומיקומו!

אם לא נקפיד עליו, הריקורסיה תהיה אין סופית!

#תרגול מהשיעור#

שאלות:

1)  כתוב פונקציה ריקורסיבית המקבלת שני מספרים שלמים a ו b.

    הפונקציה מחזירה את הכמות של המספרים הזוגיים בין a ל- b.

    לדוגמא:  עבור a=2 ,  b=11   אז הפונקציה מחזירה 5.

2) כתוב פונקציה ריקורסיבית אשר מקבלת מצביע למערך שהאיבר האחרון בו הוא 

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

3) כתוב פונקציה ריקורסיבית אשר מקבלת שני מספרים שלמים, a ו b.

    הפונקציה מחזירה את המחלק המשותף הגדול ביותר שמחלק את a  ו  b ללא 

    שארית.

  לדוגמא:

        עבור a = 30   ,    b = 75      אז הפונקציה מחזירה 15.

4) נתונה  הסדרה הבאה:

                                                                ;x1 = x  

       עבור xi זוגי                                     xi+1 = xi/2  

       עבור  xi  אי זוגי                     xi* 3 + 1   =

האיבר האחרון בסדרה הוא 1.

לדוגמא:  עבור  x = 12, נקבל הסדרה הבאה:

12, 6, 3, 10, 5, 16, 8, 4, 2, 1

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

5) כתוב פונקציה ריקורסיבית אשר מקבלת שני מצביעים לשתי מחרוזות ומעתיקה את
    המחרוזת השניה לראשונה  (strcpy).

בהצלחה!