אדם עומד על מדרכה. בכל מהלך הוא יכול להתקדם צעד אחד לכיוון ימין או צעד אחד לכיוון שמאל. הוא צריך להגיע לנקודה מסוימת שנמצאת במרחק n צעדים לכיוון ימין. אנו מעוניינים לבדוק בכמה דרכים שונות הוא יכול להגיע לנקודה זו, בעזרת k צעדים בדיוק.
בהינתן שני מספרים שלמים k ו-n יש להחזיר את מספר הדרכים האפשריות להגיע ב-k צעדים לנקודה במרחק n צעדים ימינה מהמקום בו האדם נמצא.
השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.
הפרמטרים תקינים, וכן 0 ≤ k וגם 0 ≤ n
אין צורך להחזיר את הדרכים עצמן ולא להדפיס אותו. רק להחזיר מהו מספר הדרכים.
k = 0, n = 0
1
הסבר: ישנה בדיוק דרך אחת להגיע באפס צעדים למיקום הנוכחי (להישאר במקום).
k = 4, n = 2
4
הסבר: יש ארבע דרכים שונות להגיע בארבעה צעדים לנקודה הנמצאת במרחק שני צעדים מימין למקום בו נמצא האדם והן: א. שמאל, ימין, ימין, ימין ב. ימין, שמאל, ימין, ימין ג. ימין, ימין, שמאל, ימין ד.ימין, ימין, ימין, שמאל
k = 4, n = 3
0
הסבר: אין דרך אפשרית להגיע בארבעה צעדים למטרה במרחק שלושה צעדים ימינה, כי נדרשים לפחות 3 צעדים ימינה ועוד צעד אחד לכיוון כלשהו.
k = 0, n = 1
0
הסבר: כאשר k=0 ו-n=1, לא ניתן להגיע לנקודה ללא צעדים.
k = 2, n = 2
1
הסבר: כאשר k=2 ו-n=2, יש דרך אחת: שני צעדים ימינה.
k = 3, n = 1
3
הסבר: כאשר k=3 ו-n=1, יש שלושה דרכים: שני צעדים ימינה וצעד אחד שמאלה בסדרים שונים.
k = 2, n = 0
2
הסבר: כאשר k=2 ו-n=0, יש שתי דרכים: צעד אחד ימינה וצעד אחד שמאלה בסדרים שונים.
k = 5, n = 1
10
הסבר: כאשר k=5 ו-n=1, יש 10 דרכים להגיע לנקודה עם 3 צעדים ימינה ו-2 צעדים שמאלה.
קלט:
k = 0, n = 0
הפלט המבוקש:
1