|
רקורסיה
רקורסיה הוא תהליך בו הפונקציה קוראת לעצמה.
מתכנתים מתקשים להבין את תהליך הרקורסיה ומופתעים מתוצאותיו.
זהו כלי חשוב מאוד וישנם בעיות שהפיתרון הטבעי להן הוא רקורסיה.
נראה את שני סוגי הרקורסיות: נפתח ברקורסיה לא אמיתית הנקראת רקורסית קצה בו הקריאה לפונקציה נעשית בשורה האחרונה והסיבה היא פשוטה ובסה"כ מקבלים לולאה פשוטה (נראה זאת בהמשך על ידי דוגמא) והשנייה רקורסיה אמיתית שהקריאה מופיעה בגוף הפונקציה.
 דוגמא 1:
|
#include <conio.h>
#include <stdio.h>
void s_recursion (int n) //s_recursion
{
if (n > 0)
{
printf ("%d \n\r", n);
s_recursion (n-1);
}
}
void main()
{
int n = 10;
s_recursion (n);
}
|
דוגמא לרקורסיית קצה, כפי שאמרנו רקורסיה זו זהה ללולאה פשוטה.
דוגמא 2:
|
#include <conio.h>
#include <stdio.h>
void r_recursion (int n) //real recursion
{
if (n > 0)
{
r_recursion (n-1);
printf ("%d \n\r", n);
}
}
void main()
{
int n = 10;
r_recursion (n);
}
|
זוהי דוגמא לרקורסיה אמיתית. הפונקציה r_recursion קוראת לעצמה בתחילת הפונקציה. הפלט הוא 1 עד 10 והסיבה היא שהתוכנית לא נעצרת בתנאי העצירה אלא רק באחד מעותקיה .
כשפונקציה קוראת לעצמה בעצם נוצר עותק של הפונקציה ובתוכנית שלנו נוצרו 10 עותקים. כשהאחרון מבניהם לא מקיים את תנאי העצירה הוא נסגר וכל שאר העותקים ממשיכים להתבצע במלואם מהנקודה שיצאנו מהם (במקרה שלנו משורת ההדפסה) ולכן המספרים מודפסים בסדרם ההפוך.
נסכם ונאמר: אם הקריאה לפונקציה מתבצעת באמצע הפונקציה אז לאחר שהגענו לתנאי הקצה ואנו בעותק האחרון, נסיים לבצע אותו ונחזור לעותק לפני אחרון (זה שקרא לאחרון) לשורה הבאה שלא הספקנו לבצע (עקב הקריאה לעותק הבא אחריה שהוא היה העותק האחרון) וכך נסיים אותו. משם נלך לעותק הלפני לפני, נסיים את הפקודות שלא ביצענו וכך הלאה עד אשר נגיע לעותק הראשון ונמשיך אותו מהשורה הראשונה שלא ביצענו וכך נסיים את פעולת הרקורסיה.
בעצם יש מספר תכונות לפונקציה רקורסיבית:
1. תנאי קצה - כדי שהרקורסיה תיעצר בקריאה מסוימת. זהו תנאי חשוב ביותר - אם לא נדאג לכך נקבל לולאה אינסופית.
2. קריאה לפונקציה עצמה (בדר"כ עם ערך קטן או גדול יותר).
כך למעשה ניתן לפתור בעיות רבות בעזרת רקורסיה: נתונה בעיה מסדר n מניחים קיום פיתרון לבעיה מסדרn-1 , כותבים תנאי עצירה ועל סמך אמונה של פיתרון בעיה לn-1 כותבים את הפונקציה.
לדוגמא:
חישוב עצרת של מספר n - בניית הפונקציה factorial(n):
כתיבת תנאי עצירה: if (n = 0) return 1
כלומר 0! שווה ל 1,
מניחים קיום פתרון של בעיית העצרת של n-1 כלומר factorial(n-1) ,
שלב אחרון: פתרון הבעיה:
facroaial(n) = factorial(n-1)*n
נממש את הפיתרון:
דוגמא 3:
|
#include <conio.h>
#include <stdio.h>
long factorial (int n)
{
if (n > 0)
return (n * factorial (n-1));
else
return 1;
}
void main()
{
int n = 5;
printf ("The factorial of %d is: %ld", n, factorial(n));
}
|
נוצרו 5 עותקים, האחרון לא מקיים את תנאי הקצה ולכן הערך המוחזר הוא 1. העותק האחרון הסתיים, העותק שלפניו מקבל 1 ומכפיל אותו בערכו של n (1), עותק זה מסתיים התוצאה (1) מוחזרת לעותק שנוצר לפני ושוב מכפיל בערכו של n (2), עותק זה מסתיים והתוצאה (2) נשלחת לעותק שלפניו, מוכפלת בערכו של n (3) כעת התוצאה 6 וכך הלאה עד לסיימו של העותק הראשון.
דוגמא 4:
|
#include <conio.h>
#include <stdio.h>
long fib (int n)
{
if ((n == 0) || (n ==1))
return 1;
else
return (fib (n-1) + fib (n-2));
}
void main()
{
int n = 0;
for ( ; n <= 20; n++)
printf ("Fibunachi (%d): %ld\n\r", n, fib(n));
}
|
התוכנית מחשבת את סדרת פיבונצ'י עד האיבר ה 20 שחוקיותה: שני האיברים הראשונים שווים ל- 1 וכל שאר אברי הסדרה שווים לחיבור שני האיברים שלפניהם.
דוגמא 4.1:
|
#include <conio.h>
#include <stdio.h>
long fib (int n)
{
if ((n == 0) || (n == 1))
return 1;
else
return (fib (n-1) + fib (n-2));
}
long d_fib (int n)
{
if ((n == 0) || (n == 1))
return 0;
else
return (fib (n) - fib (n-1));
}
void main()
{
int n;
for (n = 0; n <= 20; n++)
printf ("Fibunachi (%d): %ld\n\r", n, fib(n));
for (n = 2; n <= 22; n++)
printf ("Diffrance_Fib (%d): %ld\n\r", n, d_fib(n));
}
|
הרחבה של התוכנית הקודמת - נבנה את סדרת ההפרשים בין שני אברי עוקבים של סדרת פיבונצ'י.
יש לשים לב כי גם היא מהווה סדרת פיבונצ'י מהאיבר השני והלאה.
סדרה זו צופנת בחובה המון יופי ומורכבות - למתעניינים יש מספר רב של ספרים החוקרים את הסדרה המיוחדת הזו.
הדפסת קובץ הפוך:
|
void reverse (FILE *f)
{
char ch;
static temp = 0;
if ((fscanf (f, "%c", &ch)) != EOF)
reverse(f);
if (temp)
printf ("%c", ch);
temp = 1;
}
|
הפונקציה מקבלת מצביע לקובץ המבוקש. בפונקצית ההדפסה השתמשנו במשתנה סטטי temp - יחודו הוא בכך שהוא שומר על ערכו בפונקציה אפילו אם יוצאים מהפונקציה, ובפעם הבאה שנשתמש בפונקציה ערכו לא יאתחל אלא יהיה הערך האחרון שעודכן. השתמשנו במשתנה מיוחד זה מכיוון שאנו רוצים לעבור על כל הקובץ וברגע שנגיע לסוף הקובץ נדפיס את תוכנו מהסוף להתחלה. לא יהיה בכך קושי מכיוון שבכל אחד מהעותקים המשתנה ch מכיל תו אחר -ביציאה מהרקורסיה אנו נדפיס את התו האחרון ולאחר מכן את התו הלפני אחרון עד שנגיע לעותק הראשון ונדפיס את התו הראשון שקראנו.
הבעיה היא שמגיעים לתו סוף קובץ ולא מעוניינים להדפיסו ולכן המשתנה הסטטי ערכו 0 וכשמגיעים לסוף קובץ תו זה EOF) ) לא מודפס ומשנים את ערכו של המשתנה הסטטי ל 1 וכעת כל שאר התווים של הקובץ יודפסו למסך.
כעת נראה את התוכנית במלואה:
דוגמא 5:
|
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
void reverse (FILE *f)
{
char ch;
static temp = 0;
if ((fscanf (f, "%c", &ch)) != EOF)
reverse(f);
if (temp)
printf ("%c", ch);
temp = 1;
}
void main()
{
FILE *f;
char file_name[20];
printf ("Enter a file name to show reverse: ");
scanf ("%s", file_name);
if ((f = fopen (file_name, "rt")) != NULL)
reverse (f);
else
{
printf("\n\rCan't open file %s ", file_name);
exit(1);
}
}
|
דוגמא 6:
|
#include <conio.h>
#include <stdio.h>
int paskal (int i, int j)
{
if (j == 0 || j == i)
return 1;
else
return paskal (i-1, j-1)+paskal (i-1, j);
}
void main()
{
int i,j;
int leng = 9;
for (i = 0; i < leng; i++)
{
putchar ('\n');
for (j = 0; j < i+1; j++)
printf ("%d ",paskal(i, j));
}
}
|
בנית משולש פסקל בעזרת רקורסיה. הקוד קצר לעין שיעור ביחס ללולאות במקרים כאלו.
כאמור ניתן לראות את החיסכון האדיר בשורות קוד כאשר משתמשים ברקורסיה על פני לולאות. ברגע שמבינים את הרקורסיה הרבה יותר פשוט לפתור בעיות מורכבות על ידי רקורסיה מאשר מספר רב של לולאות.
אמרנו בתחילה כי ברקורסיה יש קריאות לעותקים מהפונקציה, העתקים אלו נשמרים במחסנית והקריאות משתחררות אחת אחר השנייה מהקריאה העליונה (האחרונה) עד לראשונה ומכיוון שכמות הזיכרון של המחשב מוגבלת יש מספר חסום של קריאות - כלומר אם נקרא לפונקציה יותר משיוכל המחשב לאחסן הוא ייעצר. לדוגמא אם נרצה לחשב את האיבר ה- 100 של סדרת פיבונצ'י סביר להניח שלא נוכל לעשות זאת (במחשב רגיל). לכן לא תמיד עדיף להשתמש ברקורסיה ויש לזכור שמספר הקריאות חסום.
ניתן לייצר רקורסיות מורכבות יותר על ידי כך שתהיה יותר מקריאה אחת לפונקציה בפונקציה.
יש לזכור שכאשר עותק מסתיים חוזרים לעותק שלפניו מהמקום שיצאנו ממנו.
דוגמא 7:
|
#include <conio.h>
#include <stdio.h>
void func1 (int n)
{
if (n > 0)
{
gotoxy (4*n, wherey());
printf ("Enter no_%d\n", n);
func1 (n-1);
gotoxy (4*n, wherey());
printf ("Exit no_%d\n", n);
func1 (n-1);
}
}
void func2 (int n)
{
if (n > 0)
{
gotoxy (4*n, wherey());
printf ("Enter no_%d\n", n);
func2 (n-1);
gotoxy (4*n, wherey());
printf ("Exit no_%d\n", n);
func2 (n-1);
}
}
void func3 (int n)
{
if (n > 0)
{
func3 (n-1);
gotoxy (4*n, wherey());
printf ("Enter no_%d\n", n);
gotoxy (4*n, wherey());
printf ("Exit no_%d\n", n);
func3 (n-1);
}
}
void func4 (int n)
{
if (n > 0)
{
func4 (n-1);
gotoxy (4*n, wherey());
printf ("Enter no_%d\n", n);
func4 (n-1);
gotoxy (4*n, wherey());
printf ("Exit no_%d\n", n);
}
}
void main()
{
int num = 3;
clrscr();
func1 (num);
printf("\n\n");
func2 (num);
getchar();
clrscr();
func3 (num);
printf("\n\n");
func4 (num);
getchar();
}
|
השתמשנו הפונקציה getchar על מנת שנוכל לחלק את הפלט לשני חלקים ונוכל לראות זאת על ידי השהית הפלט עד לקליטת מקש.
הצעה: רשום את ניחושיך בנוגע לפלט של התוכנית וראה אם צדקת
בתוכנית ביצענו שימוש בפונקציה gotoxy על מנת שיהיה ברור באיזה שלב ברקורסיה אנו נמצאים. ככל שהכיתוב עמוק יותר (כלומר שדה ה x גדול יותר כך אנו יותר "עמוק" ברקורסיה וההיפך).
חשוב תמיד לזכור שאפילו אם יש מספר קריאות לפונקציה ברגע שאנו חוזרים לעותקים הראשוניים אנו ממשיכים מהשורה הראשונה שהפסקנו לבצע את הפקודות באותה קריאה של הפונקציה ואף אם בהמשך יש שוב קריאה לפונקציה אנו נכנס שוב לעותקים הבאים ובקיפול (חזרה) של הרקורסיה נמשיך שוב מהשורה הראשונה שלא ביצענו בפונקציה.
|
|
 |
| © איתן 2003. כל הזכויות שמורות למערכת המידע איתן. |
|
מבחן
