מבוא מהיר לרקורסיה ב- Javascript

הפונקציה קוראת לעצמה עד שמישהו עוצר אותה.

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

רעיון ליבה

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

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

פונקצית ספירה לאחור

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

countDownFrom(5); // 5 // 4 // 3 // 2 // 1 

והנה האלגוריתם שלנו לפתור בעיה זו.

1. קח פרמטר אחד שנקרא number. זו נקודת המוצא שלנו.
2. עבור numberמטה למטה 0, רושם כל אחד בדרך.

נתחיל forבגישה של לולאה ואז נשווה אותה לגישה רקורסיבית.

גישה חובה (לולאות)

function countDownFrom(number) { for (let i = number; i > 0; i--) { console.log(i); } } countDownFrom(5); // 5 // 4 // 3 // 2 // 1 

זה מכיל שני שלבים אלגוריתמיים.

1. ✅ קח פרמטר אחד שנקרא number.
2. ✅ התחבר הכל numberעד 0.

גישה רקורסיבית

function countDownFrom(number) { if (number === 0) { return; } console.log(number); countDownFrom(number - 1); } countDownFrom(5); // 5 // 4 // 3 // 2 // 1 

זה גם עובר.

1. ✅ קח פרמטר אחד שנקרא number.
2. ✅ התחבר הכל numberעד 0.

אז מבחינה רעיונית שתי הגישות זהות. עם זאת, הם מבצעים את העבודה בדרכים שונות.

ניפוי באגים בפתרון הציווי שלנו

לדוגמא חזותית יותר, בואו נכניס debuggerגרסת לולאה שלנו ונזרוק אותה לכלי המפתחים של Chrome.

function countDownFrom(number) { for (let i = number; i > 0; i--) { console.log(i); debugger; } } 

ראה כיצד הוא משתמש במשתנה נוסף,, iכדי לעקוב אחר המספר הנוכחי? ככל שאיטרציה iיורדת, ובסופו של דבר מכה 0ומסתיימת.

ובסופו של forהלולאה אנו מצוינים "להפסיק אם i > 0".

ניפוי באגים בפתרון הרקורסיבי שלנו

function countDownFrom(number) { if (number === 0) { return; } console.log(number); debugger; countDownFrom(number - 1); } 

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

הסיבה לכך היא שכל קריאה countDownFromלהוסיף לערימה ולהאכיל אותה number - 1. על ידי כך אנו מעבירים דרך מעודכנת numberבכל פעם. אין צורך במדינה נוספת!

זה ההבדל העיקרי בין שתי הגישות.

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

אבל איך שתי הגרסאות יודעות מתי להפסיק?

לולאות אינסופיות

בנסיעותיך אולי הוזהרת מפני הלולאה האינסופית האימתנית.

? THIS RUNS FOREVER, BE WARNED ? while (true) { console.log('WHY DID YOU RUN THIS?!' } ? THIS RUNS FOREVER, BE WARNED ? for (i = 0;;) { console.log('WHY DID YOU RUN THIS?!') } 

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

✅ This does not run forever x = 0; while (x < 3) { console.log(x); x++; } ✅ This does not run forever for (x = 0; x < 3; x++) { console.log(x); } 

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

// Stop at 0 for (let i = number; i > 0; i--) 

שוב, לולאות זקוקות למצב נוסף כדי לקבוע מתי עליהם להפסיק. זה מה xו iמיועד.

רקורסיה אינסופית

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

?THIS RUNS FOREVER, BE WARNED? function run() { console.log('running'); run(); } run(); // running // running // ... 

Without a stopping condition, run will forever call itself. You can fix that with an if statement.

✅ This does not run forever function run(x) { if (x === 3) return; console.log('running'); run(x + 1); } run(0); // running // running // running // x is 3 now, we're done. 

Base case

This is known as the base case–our recursive countDownFrom had one.

if (number === 0) { return; } 

It's the same idea as our loop's stopping logic. Whichever approach you pick, always remember that at some point it needs to be stopped.

Summary

• Recursion is when a function calls itself until someone stops it.
• It can be used instead of a loop.
• If no one stops it, it'll recurse forever and crash your program.
• A base case is a condition that stops the recursion. Don't forget to add them!
• Loops use extra state variables for tracking and counting, while recursion only uses the provided parameters.

Thanks for reading

לקבלת תוכן כזה, בקר בכתובת //yazeedb.com. אנא הודיעו לי מה עוד תרצו לראות! מכשירי ה- DM שלי פתוחים בטוויטר.

עד הפעם הבאה!