דף הבית >>רקורסיות>>תכונות הרקורסיה

פרק 2

רקוקסיות

 

תכונות הרקורסיה :

 

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

    (ללא בסיס הרקורסיה לא תסתיים לעולם ).

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

 

שלבים בכתיבת ריקורסיה:

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

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

  3. יוצרים את תנאי הבסיס.

ב ++C/C תפונקצייה יכולה לקרוא לעצמה . הפונקצייה נקראת רקורקורסיבית אם יש ביטוי בגוף הפונקציה קורא לעצמו רקורסייה זה תהליך של הגדרה בתנאים של עצמו , ולפעמים נקרא הגדרה מעגלית. דוגמא פשוטה של רקורסייה זו פונקצייה זו ( )factr ,אשר מחשבת עצרת של מספר ,העצרת שלמספר n הוא התוצאה של כל המספרים בין 1 ל n .לדוגמא ,3 עצרת הוא 1*2*3 או 6 נציג זאת: 


Int factr(int n ) {
   Int answer;
   If(n= =1) return (1);
   Answer = factr (n-1) *n;  /קורא לפונקציה**/
   Return(answer);
}

בצורה לא רקורסיבית: 


  Int fsct(int n) {
  Int t ,answer;
  For (t=1; t<=n;t++)
       Answer=answer*(t);
  Return (answer);
}

הפונקציה הלא רקורסיבית ( ) fact אמורה להיות ברורה.אנו משתמשים בלולאה אשר רצה מ 1 עד n ומכפילה כל מספר בכל במספר הבא עד סוף הלולאה.הפעולה של הפונקציה הרקורסיבית ( ) fact קצת יותר מורכב , מתי שנקרא ל( ) factr אם ארגומנט 1, הפונקציה תחזיר 1.אחרת , היא מחזירה את התוצאה של factr ( n - 1 ) * n בכדי להאריך את התוצאה ,( ) factr נקרא אם 1-n .זה קורה עד שn שווה ל1 והקריאות של הפונקציה מתחילות לחזור.חישוב של עצרת 2 ,הקריאה הראשונה ל ( ) factr קורא לרקורסיה השניה אם הארגומנט 1.קריאה זו מחזירה ,ומוכפל ב 2 .התשובה אם כן היא 2 .תנסה לעבוד בעצמך על 3 עצרת.מתי שפונקציה קוראת לעצמה משתנים ופרמטרים חדשים מאותרים באיחסון במחסנית,והקוד של הפונקציה מוצא מהראש ע"י הפרמטרים החדשים ,קריאה רקורסיבית לא יוצרת העתקה מחודשת של הפונקציה , רק הפרמטרים המופעלים הם חדשים .כאשר הפונקציה חוזרת המשתנים והפרמטרים הלוקלים הישנים נמחקים מהמחסנית בנקודה שבא נקראה הפונקציה בתוך הפונקציה הקיימת.רוב הפונקציות הרקורסביות לא מפחיתות בצורה משמעותית את גודל הקוד או שמשפרת את הזיכרון ,וגם רוב הגירסאות לפונקציות רקורסביות פעולתם קצת איטית לעומת הפונקציות ששקולות להם.היתרון לפונקציות רקורסביות שאתה יכול להשתמש בהם בצורה ברורה ופשוטה במספר אלגוריתמים לדוגמא quicksort אלגוריתם קשה להשמה בפונקציה רגילה במיוחד מה שקשור לבינה מלאכותית.

 

דוגמא נוספת: 

#include <iostream.h>

void reverse(char const *source)
{
if (*source)  
     {
     reverse(source+1);
     cout<<*source;
     }
}  
main()
{
char name[10]="shalom";
reverse(name);
return 0;
}

( )Main קוראת לפונקציה reverse עם שם הווקטור כפרמטר. שם הווקטור מצביע על האיבר הראשון בווקטור.מכוון ש s* שונה מ 0 (null מסיים) ,תתבצע קריאה רקורסיבית לפונקציה עוד לפני הפלט,כאשר המצביע שהוא הפרמטר ,מצביע על האיבר השני. כש *s שווה לאפס לא תתבצע קריאה רקורסיבית והפונקציה תסתיים .עם סיום הפונקציה חוזרים לפונקציה שקראה לה ,שהיא פקודה אחת אחרי הקריאה הרקורסיבית.פקודה זו שולחת לפלט את התו 'm' והפונקציה מסתיימת .חוזרים שלב אחד אחורה ,בו נרשם התו 'o' ושוב הפונקציה מסתיימת וכך חוזרים על כל אחד מהקריאות.המחרוזת נרשת בצורה הפוכה עד אשר מגיעים ל main ואז מסתיימת התוכנית.לכמות הקריאות של הפונקציה לעצמה ,לפני שהסתיימה קריאה קודמת ,אנו קוראים עומק רקורסיה.

 

c דוגמא נוספת המחשבת את סכום המספרים עד הפרמטר. 

#include <iostream.h>
sum(int n)
  {
  if (n==1) return(1);
    else
     return(n+sum(n-1));
  }
main()
{
cout<<sum(5)<<'\n';
return 0;
}
 

הפונקציה מחזירה את הסכום של n עם הערך המוחזר של הפונקציה מסדר אחד נמוך יותר. ז"א מסתמכים שהפונקציה sum יודעת למצא את הסכום של המספרים עד ל1-n,מסתצכים על כך כדי לבצע את שלב ה-n בהנחה ש (sum(n-1 נותן את הסכום של המספרים עד ל1-n,אזי ל-n נותר לבצע רק את הפעולה הבאה :

(n+sum(n-1. בסיס הרקורסיה יהיה (sum(1 כיוון שחישוב סכום המספרים עד 1 הוא מיידי ואינו דורש קריאה רקורסיבית נוספת.

 

הקודם
הבא