רקורסיה

[darkstar]

רקורסיה

מישהו מוכן להסביר לי מזה ולמה זה טוב? אולי להפנות אותי למאמר?

 

[חובבן]

רקורסיה היא התייחסות עצמית

או בתכנות, קריאה של פונקציה לעצמה.

 

[עידית_]

ולמה זה טוב? בעיקר

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

 

[מושון_עם_הקטן]

אילו פונקציות למשל?

 

[עידית_]

הדוגמה הכי קלאסית היא

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

 

[מושון_עם_הקטן]

אם כל הכבוד

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

 

[עידית_]

קודם כל

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

int fib { return fib(n-1) + fib(n-2); } תכתוב את זה עכשיו עם לולאה, ותראה שכל ה"הגיון" שמאחורי הפונקציה הולך לאיבוד. אם לא הבנתי אותך, אז תסביר שוב.​

 

[עידית_]

כמובן עם תנאי עצירה

if (n==1) return 1; if (n==2) return 2;​

או תנאי אחר, לפי איך שרוצים להגדיר...

 

[zivki]

מאמר