ex1.3 רקורסיה במערך

האם יש איבר זוגי במערך?

כתוב פונקציה bool EvenExists (int[] arr) שמחזירה true אם קיים איבר זוגי במערך, אחרת false

public static bool EvenExists(int[] arr, int i = -2)
{
    if (i == -1)
        return false;
    else if (i == -2)
        return EvenExists(arr, arr.Length - 1);

    // ממש משנה הסדר: אם הבדיקת מודולו אחרי הקריאה הרקורסיבית
    // (  הקוד יבצע הרבה פעולת מיותרות (יריץ רקורסיה על כל המערך תמיד
    else //  את מה שכאן חייבים לכתוב הפוך!!!!!!!!!!!!!!
        return EvenExists(arr, i - 1) || arr[i] % 2 == 0; //= מימוש גרוע
}

חיפוש בינארי רקורסיבי

link

עליכם לממש פונקציה רקורסיבית בשם BinarySearch ב-C# עם הכותרת:public static int BinarySearch(int[] arr, int target)

הפונקציה מקבלת שלושה פרמטרים:

1. arr - מערך ממוין של מספרים שלמים.
2. target - המספר השלם שיש לחפש במערך.

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

התנהגות הפונקציה:

1. אם target נמצא במערך, הפונקציה תחזיר את האינדקס הראשון שבו הוא מופיע.
2. אם target אינו נמצא במערך, הפונקציה תחזיר -1.

הערות חשובות למימוש:

1. השתמשו בפרמטרים האופציונליים left ו-right. הפונקציה צריכה להיות ניתנת לקריאה גם עם שני פרמטרים בלבד (arr, target).
2. בתוך הפונקציה, אם right הוא -1 (ערך ברירת המחדל בקריאה הראשונית), עליכם לאתחל אותו לאינדקס האחרון של המערך (length - 1).
3. האלגוריתם חייב להיות רקורסיבי.
4. אין צורך לטפל במקרים שבהם המערך אינו ממוין או מכיל איברים כפולים מעבר לבדיקה שהערך קיים או לא.

מציאת אינדקס ראשון באמצעות רקורסיה

link

עליכם לממש פונקציה רקורסיבית בשם FindFirstIndex בשפת C#, בעלת החתימה הבאה:

public static int FindFirstIndex(int[] arr, int target)

הפונקציה צריכה לקבל שלושה פרמטרים:

1. arr (int[]) - המערך שבו יש לחפש.
2. target (int) - הערך שיש למצוא את האינדקס הראשון שלו.

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

דגשים:

1. השתמשו בגישה רקורסיבית בלבד לפתרון הבעיה.
2. הפונקציה צריכה להיות static ולקבל את הפרמטרים כפי שצוין.
3. שימו לב לטיפול במקרי הבסיס של הרקורסיה.

היפוך מערך באמצעות רקורסיה

link

עליכם לממש פונקציה בשם ReverseString אשר מקבלת פרמטר אחד: str - מחרוזת להיפוך

הפונקציה צריכה להחזיר את המחרוזת הפוכה באמצעות רקורסיה.

דגשים חשובים:

1. הפונקציה חייבת להיות רקורסיבית
2. מקרה הבסיס: מחרוזת ריקה או עם תו אחד
3. במקרה הרקורסיבי: קחו את התו הראשון והעבירו אותו לסוף המחרוזת ההפוכה של השאר

טכניקת פתרון:

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

סכום איברי מערך רקורסיבי

link

עליכם לממש פונקציה רקורסיבית ב-C# בשם SumArray אשר מקבלת מערך של מספרים שלמים arr.

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

חתימת הפונקציה:

public static int SumArray(int[] arr)

דגשים:

1. יש להגדיר מקרה בסיס שיעצור את הרקורסיה.
2. יש לבצע קריאה רקורסיבית שתתקדם במערך.

הדפסת מערך בסדר הפוך (רקורסיה)

link

עליכם לממש פונקציה רקורסיבית ב-C# בשם PrintArray עם החתימה הבאה:

public static void PrintArray(int[] arr)

הפונקציה צריכה לקבל מערך של מספרים שלמים (arr)

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

דגשים:

1. הפונקציה חייבת להיות רקורסיבית.
2. יש להשתמש בפרמטר index כדי לעקוב אחר המיקום הנוכחי במערך.
3. ודאו שההדפסה היא בסדר הפוך.
4. אין צורך לטפל במקרה של מערך ריק או באינדקסים חורגים; המערך יכיל תמיד מספרים שלמים חיוביים.

מיון מיזוג (Merge Sort)

link

עליכם לממש את הפונקציה הרקורסיבית MergeSort בשפת C#:

public class Solution
{
    public static void MergeSort(int[] arr)
    {
        // Implement your recursive Merge Sort logic here
    }

}

תיאור הפונקציה: הפונקציה MergeSort מקבלת arr מערך של מספרים שלמים שיש למיין.

דרישות:

1. השתמשו באלגוריתם מיון מיזוג (Merge Sort).
2. הפתרון חייב להיות רקורסיבי עבור שלבי החלוקה.
3. יש לממש פונקציית עזר למיזוג (Merge).
4. הפונקציה אינה מחזירה ערך אלא ממיינת את המערך הנתון במקום (in-place modification).

תהליך מיון מיזוג:

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

ספירת מספרים זוגיים במערך רקורסיבית

link

עליכם לממש פונקציה רקורסיבית ב-C# בשם CountEven עם החתימה הבאה:static int CountEven(int[] arr)

הפונקציה מקבלת arr - מערך של מספרים שלמים.

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

דגשים:

1. הפתרון חייב להיות רקורסיבי. אין להשתמש בלולאות (for, while, foreach).
2. השתמשו במקרה הבסיס כשהאינדקס מגיע לסוף המערך.

האיבר הגדול ביותר במערך (רקורסיבי)

link

עליכם לממש פונקציה רקורסיבית ב-C# בשם MaxArray בעלת החתימה הבאה:

static int MaxArray(int[] arr)

הפונקציה תקבל arr - מערך של מספרים שלמים.

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

הנחיות למימוש הרקורסיה:

1. מקרה בסיס: אם הגעתם לאינדקס האחרון במערך (index == arr.Length - 1), החזירו את הערך באינדקס זה.
2. שלב רקורסיבי: השוו את הערך הנוכחי ב-arr[index] עם הערך המקסימלי שנמצא בשאר המערך (החל מ-index + 1). ניתן לעשות זאת על ידי קריאה רקורסיבית לפונקציה MaxArray עם index + 1.
3. החזירו את הערך המקסימלי שנמצא בהשוואה.

דגשים:

1. הפונקציה חייבת להיות רקורסיבית.
2. אין להשתמש בלולאות (for, while) בתוך הפונקציה.
3. אין לטפל במקרה של מערך ריק.

בדיקת מערך ממוין רקורסיבית

link

עליכם לממש פונקציה רקורסיבית ב-C# בשם IsSorted בעלת החתימה הבאה:

public static bool IsSorted(int[] arr)

הפונקציה מקבלת arr - מערך של מספרים שלמים.

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

דגשים:

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

חיפוש איבר במערך רקורסיבי

link

עליכם לממש פונקציה רקורסיבית ב-C# בשם SearchArray עם החתימה הבאה:

public static bool SearchArray(int[] arr, int target)

הפונקציה מקבלת שני פרמטרים:

1. arr (int[]): המערך שבו יש לחפש.
2. target (int): הערך שאתם מחפשים במערך.

הפונקציה צריכה להחזיר:

1. true אם הערך target נמצא במערך arr.
2. false אם הערך target לא נמצא במערך arr.

דגשים:

1. הפונקציה חייבת להיות רקורסיבית (אין להשתמש בלולאות).
2. יש לטפל במקרה הבסיס הרקורסיבי.

חיפוש רקורסיבי של איבר במערך לא ממויין

link

עליכם לממש פונקציה רקורסיבית ב-C# בשם SearchArray עם החתימה הבאה:

public static bool SearchArray(int[] arr, int target) הפונקציה מקבלת שלושה פרמטרים:

1. arr (int[]): המערך שבו יש לחפש.
2. target (int): הערך שאתם מחפשים במערך.

הפונקציה צריכה להחזיר:

1. True אם הערך target נמצא במערך arr.
2. False אם הערך target לא נמצא במערך arr.

דגשים:

1. הפונקציה חייבת להיות רקורסיבית (אין להשתמש בלולאות).
2. יש לטפל במקרה הבסיס הרקורסיבי.