שיעור 16: רקורסיה

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

דוגמא פשוטה לרקורסיה תהיה:

void recurse()
{
  recurse(); //Function calls itself
}

int main()
{
  recurse(); //Sets off the recursion
  return 0;  //Rather pitiful, it will never be reached
}

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

#include <iostream.h>
void recurse(int count) //The count variable is initalized by each 
			//function call
{
  cout<<count;  
  recurse(count+1); //It is not necessary to increment count
//each function's variables
}	//are separate (so each count will be initialized one greater)

int main()
{
  recurse(1);        //First function call, so it starts at one
  return 0;          
}

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

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

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

דוגמא מהירה:

void doll(int size)
{
  if(size==0)	//No doll can be smaller than 1 atom (10^0==1) so doesn't 
		//call itself
    return;    //Return does not have to return something, it can be used 
				//to exit a function
  doll(size-1);  //Decrements the size variable so the next doll will be 
		 //smaller.
}

int main()
{
  doll(10);   //Starts off with a large doll (its a logarithmic scale)
  return 0;   //Finally, it will be used
}

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

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

void printnum(int begin)
{
  cout<<begin;
  if(begin<9)  //The end condition is when begin is greater than 9
    printnum(begin+1);    //for it will not recurse after the if-statement
  cout<<begin;  //Outputs the second begin, after the program has 
						//gone through and output
}		//the numbers from begin to 9.

פונקציה זו עובדת כיוון שהיא תעבור ותדפיס את המספרים begin עד 9, ואז כאשר כל פונקציה printnum מסתיימת היא תמשיך להדפיס את הערך של begin בכל פונקציה מ 9 עד begin.

זה רק ההתחלה של התועלת של הרקורסיה. הנה אתגר קטן, השתמש ברקורסיה כדי לכתוב תוכנית שמחזירה עצרת של כל מספר שגדול מ 0. (עצרת זה מספר * (1-המספר) * (2-המספר)...* 1).

רמז: מצא ברקורסיה את העצרת של המספרים הקטנים יותר קודם, כלומר, התוכנית לוקחת מספר, מוצאת את העצרת של המספר הקודם, וכופלת את המספר בעצרת שלו...תהנה, ותשלח לי email ל webmaster@cprogamming.com אם הבנת.

לדף הראשון

<< לדף הקודם

לדף הבא >>