Let's learn C

רקורסיות

רקורסיה היא שיטה לפתרון בעיות גדולות באמצעות פתרון של בעיות קטנות יותר.
ננסה להבין את ההסבר על הרקורסיה באמצעות דוגמא:
נניח שאנו רוצים לבדוק כמה פעמים המספר 32 מתחלק ב 2.
אנו נניח שאנחנו לא יודעים כמה פעמים 32 מתחלק ב 2 ואז ננסה לפתור את הבעיה הגדולה הזאת עם בעיה קטנה יותר.
כלומר, אם נחלק את 32 ב-2 פעם אחת נקבל 16.
כעת, הבעיה שלנו היא לא כמה פעמים 32 מתחלק ב 2 אלא כמה פעמים 16 מתחלק ב-2.
אם נדע כמה פעמים 16 מתחלק ב2 אזי נדע כמה פעמים 32 מתחלק ב2, כי 16*2=32.
בשלב זה, נניח שאנו לא יודעים כמה פעמים 16 מתחלק ב2 אז אנו נחלק ב2 פעם נוספת ונקבל 8.
ואם נחלק את 8 ב-2 פעם נוספת נקבל 4. אחר כך נקבל 2 ואז 1.
כעת, הגענו ל 1 -> אנו לא יכולים לחלק ב2 יותר ולכן נספור כמה פעמים ביצענו את החילוק.
1->2->4->8->16->32 כלומר, ביצענו את החילוק 5 פעמים ולכן 32 מתחלק ב-2 חמש פעמים.

איך מממשים דבר כזה?

אז לפני שנקפוץ לפתרון כדאי שנחשוב על כמה דברים:

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

שימו לב!

אם אתם נתקעים על השאלה "מהו תנאי העצירה?" נסו לחשוב "מתי אני מפסיק לעשות את הפעולה הזאת?" או "מה הבעיה הקטנה ביותר שמסתתרת מאחורי השאלה?"
אם אתם נתקעים בשאלה השנייה תנסו לחשוב "מה שונה בין כל שלב ושלב?" אחרי שחשבנו נסתכל על השאלה וננסה להבין מה אנחנו אמורים לקבל חזרה? -> מה הפונקציה מחזירה? האם זה מספר? תו? או בכלל כלום?

בשאלה שלנו:

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

כעת, לאחר שאנחנו יודעים את כל השלבים נסתכל על המבנה הבא:

מספר הערות:

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

CODE:


#include <stdio.h>
int DevideByTwo(int n)
{
  if(n % 2 != 0)
  {
    return 0; // base case.
  }
  else
  {
    return 1 + DevideByTwo(n/2); // Making the problem smaller
  }
}