Рекурсия ведет себя непредсказуемым образом с Java

Question

Я студент, и я работал над следующей задачей: найти подстроку (иглу) в большей строке (стог сена) без использования метода substring и используя рекурсию. Рекурсия не мой конек, но я выработал следующее:

public class Contains 
{ 
    public static void main(String[] args) 
    { 
     System.out.println(contains("Java programming", "ogr", false)); 
    } 

    public static boolean contains(String haystack, String needle, boolean doesContain) 
    { 
     if(haystack.length() < needle.length()) 
     { 
      return false; 
     } 
     else 
     { 
      for(int i = 0; i < needle.length(); i++) 
      { 
       if(haystack.charAt(i) != needle.charAt(i)) 
        if((i + 1) == needle.length()) 
         { 
          doesContain = false; 
          break; 
         } 
        else 
         break; 
       else 
        if((i + 1) == needle.length()) 
        { 
         doesContain = true; 
         break; 
        } 
        else 
         continue; 
      } 
      char[] haystackChar = haystack.toCharArray(); 
      char[] newCharArray = new char[(haystackChar.length - 1)]; 

      for(int j = 1; j < haystackChar.length; j++) 
      { 
       newCharArray[j - 1] = haystackChar[j]; 
      } 

      String newStr = new String(newCharArray); 

      if(doesContain == false) 
       contains(newStr, needle, doesContain); 
     } 
     return doesContain; 
    } 
} 

Я понимаю, что это не может быть лучшим или наиболее элегантным решением, но я в основном просто пытаюсь заставить его работать. Я запускаю его в отладчике Eclipse, и все работает так, как ожидалось, до вызова if(doesContain == false) во время вызова метода на contain, где doesContain имеет значение true во время итерации цикла for. Отладчик показывает значение doesContain, чтобы (правильно) быть истинным, и показывает, что он пропускает оператор if и выходит из блока else. Однако сразу после этого он перескакивает обратно в блок else и только вызывает рекурсивный вызов contain вместо того, чтобы возвращать doesContain. Затем он продолжает работать рекурсивно, а затем терпит неудачу и возвращает false, потому что теперь он просматривает остальную часть строки, где «игла» не находится.

Я знаю, что StackOverflow не является «домашней помощью», но я программирую для других целей, кроме школы, и я совершенно недоумеваю, почему он ведет себя таким образом. Кто-нибудь знает, почему он это делает? Я что-то упустил?

Answer 1

Я посмотрел через код и запустил его в затмить себя. Теория, которую вы захотите изучить, - это то, как складываются работы в рекурсии. Ваша программа находит правду, а затем выходит из стека, но к этому моменту она повторялась несколько раз. Он вернул значение true, но затем продолжил возвращать все ложные переменные, которые были сохранены до него.

Если у вас есть дополнительные вопросы, пожалуйста, дайте мне знать.

EDIT Если вы действительно заинтересованы в получении в продвинутую рекурсию я настоятельно рекомендую это видео: Java Recursion

Эй, мне не нужно идти так далеко, чтобы заставить его работать. Вы можете удалить hasContain в качестве параметра и установить его как статическую переменную экземпляра, и это сработало для меня.

public class Contains 
{ 

    private static boolean doesContain = false; 

    public static void main(String[] args) 
    { 
     System.out.println(contains("Java programming", "ogr")); 
    } 

    public static boolean contains(String haystack, String needle) 
    { 
     if(haystack.length() < needle.length()) 
     { 
      return false; 
     } 
     else 
     { 
      for(int i = 0; i < needle.length(); i++) 
      { 
       if(haystack.charAt(i) != needle.charAt(i)) 
        if((i + 1) == needle.length()) 
         { 
          doesContain = false; 
          break; 
         } 
        else 
         break; 
       else 
        if((i + 1) == needle.length()) 
        { 
         doesContain = true; 
         break; 
        } 
        else 
         continue; 
      } 
      char[] haystackChar = haystack.toCharArray(); 
      char[] newCharArray = new char[(haystackChar.length - 1)]; 

      for(int j = 1; j < haystackChar.length; j++) 
      { 
       newCharArray[j - 1] = haystackChar[j]; 
      } 

      String newStr = new String(newCharArray); 

      if(doesContain == false) 
       contains(newStr, needle); 
     } 
     return doesContain; 
    } 
} 

То, что вы были очень близок, но, передав его в качестве параметра вы хранили каждый раз, когда вы прошли через другую рекурсию. Таким образом вы возвращаете только свое окончательное значение.

Answer 2

Чтобы найти needle в haystack так, как вы хотите, вам не нужно использовать рекурсию.

Просто удалите следующие строки кода из вашей функции, и он будет работать нормально:

 char[] haystackChar = haystack.toCharArray(); 
     char[] newCharArray = new char[(haystackChar.length - 1)]; 

     for(int j = 1; j < haystackChar.length; j++) 
     { 
      newCharArray[j - 1] = haystackChar[j]; 
     } 

     String newStr = new String(newCharArray); 

     if(doesContain == false) 
      contains(newStr, needle, doesContain); 

Answer 3

Я думаю, что вы вроде спутать себя с рекурсивной функцией. Одна из переменных, переданных рекурсивной функции, - doesContain, но функция должна вернуть, содержит ли строка ее! В строках

 if(doesContain == false) 
      contains(newStr, needle, doesContain); 

Вызов contains вернется, если подстрока содержит иглу. Вам нужно принять это значение и вернуть его обратно в стек вызовов.

Надеюсь, это имело смысл. Если это не так, я дам вам код, чтобы вы могли понять его из себя:

public static boolean contains(String haystack, String needle) 
{ 
    if(haystack.length() < needle.length()) 
    { 
     return false; 
    } 
    else 
    { 
     boolean doesContain=false; 
     for(int i = 0; i < needle.length(); i++) 
     { 
      if(haystack.charAt(i) != needle.charAt(i)) 
       if((i + 1) == needle.length()) 
        { 
         doesContain = false; 
         break; 
        } 
       else 
        break; 
      else 
       if((i + 1) == needle.length()) 
       { 
        doesContain = true; 
        break; 
       } 
       else 
        continue; 
     } 
     char[] haystackChar = haystack.toCharArray(); 
     char[] newCharArray = new char[(haystackChar.length - 1)]; 

     for(int j = 1; j < haystackChar.length; j++) 
     { 
      newCharArray[j - 1] = haystackChar[j]; 
     } 

     String newStr = new String(newCharArray); 

     if(doesContain == false) 
      return contains(newStr, needle); 
     else 
      return true; 
    } 
}