היי חברים!

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

כתבו פונקציה רקורסיבית המקבלת מערך של מספרים שלמים (arr), את מספר האיברים בו (size) ומספר שלם נוסף sum. אם קיימת תת-סדרה מתאימה שסכום איבריה הוא sum , הפונקציה מדפיסה את איבריה (בסדר כלשהו) ומחזירה 1, אחרת הפונקציה מחזירה 0.

תודה רבה!

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

אבל איך אני עושה את זה שאם זה חלק מסדרה או לא?

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

יש פה הרבה מאוד אפשרויות שגורם לזה מזמן לא להיות רקורסיה.

הנה רעיון כללי לגישה לרקורסיה:

נניח שהמערך באורך n. עכשיו, תחשוב שיש לך פונקציית "קופסה שחורה" (כלומר אתה לא יודע איך היא עובדת, אבל היא עובדת) שפותרת את הבעיה עבור מערך בגודל n-1. אז איך תפתור את השאלה?

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

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