מהו רקורסיה?

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

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

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

רוצים דוגמה:
"אם הבנת מהי רקורסיה, חזור אל הדף ממנו הגעת. אם לא – קרא בדף זה מהי רקורסיה".

הדוגמה הזו מסבירה בדיוק את הרקורסיה, כי תנאי העצירה הוא "אם הבנת.." ,בעוד ש"אם לא" אז חוזרים לאותה דוגמה כדי ללמוד מהי רקורסיה מחדש ולבסוף מבינים שהרקורסיה היא מה שאתה מתבקש לעשות...
מתכנתים משתמשים הרבה ברקורסיה. הם מתארים פונקציה רקורסיבית כ"פונקציה שקוראת לעצמה". נכון היה יותר לומר שפונקציה כזו קוראת לעותק של עצמה אבל בכל מקרה הפונקציה הזו קוראת לעצמה בלולאה (Loop) עד שלא ניתן יותר לעשות זאת - כלומר, יש תנאי יציאה שמבטיח שהיא לא תעשה את זה עד אינסוף ויהיה stack overflow...

לרוב נותנים לרקורסיה כזו את הדוגמה של חישוב n-עצרת במתמטיקה (=מכפלת 1 כפול 2 כפול 3… עד כפול n).

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

הנה הסבר יפה לרקורסיה עם דוגמה קולנועית:

סרטון שמדגים איך רקורסיה עובדת כשעושים בעזרתה גרפיקה ממוחשבת:

כניסה פנימה לפרקטל - צורה גרפית שנקראת "משולש סירפינסקי" ונבנתה בפונקציה רקורסיבית:

בקצרה:

והסבר למתכנתים (עברית):

סרט באורך מלא

צפו בנחת כדי ללמוד לעומק את הנושא: