3.4 רקורסיות

מבנה נתונים ואלגוריתמים

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

3.4.1 פונקציות רקורסיביות

פונקציות מתמטיות רבות יכולות להיות מוגדרות בצורה רקורסיבית:

· עצרת

· פיבונאצ'י

· ה-GCD של אוסליד (מכנה משותף מקסימלי)

· טרנספורמציית פורייה (Fourier Transform)

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

3.4.2 דוגמא: פקטוריאל

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

factorial( n ) = if ( n = 0 ) then 1
 else n * factorial( n-1 )

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

function fact( int n )
 {
 if ( n == 0 ) return 1;
 else return n*fact(n-1);
 }

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

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

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

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

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

בהתאם להגדרות הבאות:

fib( n ) = if ( n = 0 ) then 1
 if ( n = 1 ) then 1
 else fib( n-1 ) + fib( n-2 )

ניתן לכתוב זאת כך:

function fib( int n )
 {
 if ( (n == 0) || (n == 1) ) return 1;
 else return fib(n-1) + fib(n-2);
 }

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

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

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

מושגים

תנאי עצירה

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

המשך ל: חיפוש חזור ל: תוכן עניינים