יש לי תרגיל שבוא אני מקבל 2 מערכים למשל [d, e] ומערך שני [a, b, c, d, e, f]

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

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

זה בעיקרון הקוד שלי רק אני אמור לרשום אותו ברקורסיה ללא לולאות:

/

**
 * This class contains functions for array manipulations.
 * 
 * @author Roman
 *
 */
public class ArrayUtils {


  /**
   * Finds a sub array in a large array
   * 
   * @param largeArray
   * @param subArray
   * @return index of sub array
   */
  public int findArray(int[] largeArray, int[] subArray) {


    /* If any of the arrays is empty then not found */
    if (largeArray.length == 0 || subArray.length == 0) {
      return -1;
    }


    /* If subarray is larger than large array then not found */
    if (subArray.length > largeArray.length) {
      return -1;
    }


    for (int i = 0; i < largeArray.length; i++) {
      /* Check if the next element of large array is the same as the first element of subarray */
      if (largeArray[i] == subArray[0]) {


        boolean subArrayFound = true;
        for (int j = 0; j < subArray.length; j++) {
          /* If outside of large array or elements not equal then leave the loop */
          if (largeArray.length <= i+j || subArray[j] != largeArray[i+j]) {
            subArrayFound = false;
            break;
          }
        }


        /* Sub array found - return its index */
        if (subArrayFound) {
          return i;
        }


      }
    }


    /* Return default value */
    return -1;
  }


}

אתה לא חושב בצורה רקורסיבית.

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

לדוגמא - סכום של איברי מערך הוא בעיה גדולה, והפירוק הוא סכום של האיבר הראשון עם יתר אברי המערך.

פתרון איטרטיבי:

sum+= arr[i];

for(int i = 0; i < arr.length; i++)

פתרון רקורסיבי:

int sum(int[] arr)
{
   if (arr.length <= 0)
      return 0;
   else 
      {
      int[] subarr = new int [arr.length -1];
      System.arraycopy(arr, 1, subarr , 0, arr.length -1);
      return arr[0] + sum(subarr);
      }
}

תנסה לחשוב בצורה הזאת.

אם תגדיר את הבעיה כרקורסיבית, יהיה לך הרבה יותר קל לתרגם אותה לקוד רקורסיבי.

לא יודע, אני לא מצליח לחשוב על משהו באמצעות רקורסיה

מה ההגדרה בדיוק של "תת מערך"? האם האיברים בתת המערך צריכים להופיע ברצף או שלא? (דהיינו, האם [c,e] הוא תת מערך של [a,b,c,d,e,f]?) האם הם צריכים להופיע באותו הסדר?

כן הם צריכים להופיע באותו הסדר בדיוק.

בדוגמא שנתת זה לא תת מערך ובדוגמא שלי בהודעה הראשונה זה כן תת מערך.

התחלתי לחרבש משהו אבל יש עוד עבודה ואני די תקוע (אסור לי להשתמש בלולאות בשיטה הרקורסיבית אבל לקרוא לשיטה פרטית שעושה את זה מותר):

    public static bool findSequence(char[] findIn, char[] toFind)
    {
      return compare(findIn, toFind, num);
    }


    private static int num = 0;


    private static bool compare(char[] findIn, char[] toFind, int num)
    {
      for (int i = 0; i < findIn.Length; i++)
      {
        if (toFind[i] != findIn[num])
        {
          num++;
          return false;
        }
      }


      num++;
      return true;
    }

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

תנסה את הקוד הזה, תראה איך הוא בנוי, ותוודא שאתה מבין.

public boolean SubString(char[] arr, char[] arr2)
	{
		boolean b=false;
		if (SubStr(arr,arr2, arr.length-1, arr2.length-1,b))
			return true;
		else
			return false;
	}

	public boolean SubStr(char[] arr, char[] arr2, int len1, int len2, boolean b)
	{
		if ((b) && (len1 < 0))
			return true;
		if ((b) && (len1 >= 0))
			return SubStr(arr, arr2, len1, arr2.length-1, false);
		if ((len1 < 0) && (!b))
			return false;
		if ((len2 < 0) && (!b))
				return false;
		if (arr[len1] == arr2[len2])
			return SubStr(arr, arr2, len1-1, len2-1, true);
		else
			return SubStr(arr, arr2, len1, len2-1, false);
	}