Как работает рекурсивная функция isPalindrome? - PullRequest
Новая
       12

Как работает рекурсивная функция isPalindrome?

6 голосов
/ 02 февраля 2012

Я работаю над некоторыми начальными проблемами рекурсии, и у меня есть уточняющий вопрос, на который я хотел бы получить ответ. Самый неприятный вопрос, который у меня есть, - как эта рекурсия работает в решенной проблеме ниже?

Несмотря на то, что я решил проблему, я просто не понимаю, как рекурсивный вызов пробивается внутрь строки. Из простого просмотра кода может показаться, что этот метод будет проверять только два символа на каждом конце данной строки, без проверки остальных. Мой учебник дает крайне неудовлетворительный ответ, по сути, не беспокойтесь о том, как работает рекурсия, пока ваше выражение return решает проблему. Но мне трудно понять, как подходить к последующим проблемам рекурсии, не понимая, как можно отследить рекурсивный метод таким же образом, как и цикл.

Любые слова мудрости будут высоко оценены.

Спасибо! 

public class isPalindrome {

public static boolean isPalindrome(String str)
{
    //test for end of recursion
    if(str.length() < 2) {return true;}

    //check first and last character for equality
    if(str.charAt(0) != str.charAt(str.length() - 1)){return false;}

    //recursion call 
    return isPalindrome(str.substring(1, str.length() - 1));
}
public static void main(String[] args)
{
    System.out.print(isPalindrome("deed"));
}
}

Ответы [ 2 ]

11 голосов
/ 02 февраля 2012

Функция isPalindrome () рекурсивно вызывается для str.substring (1, str.length () -1). Таким образом, стек вызовов будет выглядеть следующим образом для вызовов isPalindrome (): 

1. isPalindrome("abcddcba"): 

   ("a" == "a") = true, so recurse

2. isPalindrome("bcddcb"):

   ("b" == "b") = true, so recurse

3. isPalindrome("cddc"):     

   ("c" == "c") = true, so recurse

4. isPalindrome("dd"): 

   ("d" == "d") = true, so recurse  

6. isPalindrome(""):           

   length < 2, so return true

Возвращаемое значение последнего вызова будет распространяться до самого верха.

С рекурсией картинки всегда помогают. Делайте все возможное, чтобы нарисовать стека вызовов в виде диаграммы. Это позволит вам визуализировать и, следовательно, лучше понимать более сложные рекурсии. Это простая «линейная» рекурсия, но в конечном итоге вы столкнетесь с «деревом», как рекурсия.

Вот картинка, которая иллюстрирует эту проблему для вас, чтобы лучше визуализировать:

Palindrome recursion

8 голосов
/ 02 февраля 2012

Вспомните о палиндроме: 

risetovotesir

Это можно построить, начав с палиндрома v (односимвольная строка - это всегда палиндром, как и пустая строка) и добавив одну и ту же букву вперед и назад: 

      v           Start with palindrome 'v'.
     ovo          Add 'o' to both ends.
    tovot         Then 't'.
   etovote        Then 'e'.
  setovotes       Then 's'.
 isetovotesi      Then 'i'.
risetovotesir     And finally 'r'.

Процесс, используемый этой рекурсивной функцией, идет в обратном направлении, разбивая строку по частям. Он определяет, действительно ли это палиндром, если оба:

  • первый и последний символы равны; и
  • внутренняя часть строки (после удаления этих двух) - палиндром.

Следовательно, код можно записать как: 

public static boolean isPalindrome (String str) {
    // Zero- or one-character string is a palindrome.

    if (str.length() < 2)
        return true;

    // If first and last characters are different, it's NOT palindromic.

    if (str.charAt (0) != str.charAt (str.length() - 1))
        return false;

    // Otherwise it's palindromic only if the inner string is palindromic.

    return isPalindrome (str.substring (1, str.length () - 1));
}

Используя строку peed deep, различные уровни: 

1. length 9 >= 2, both ends are 'p', next level checks 'eed dee'.
2. length 7 >= 2, both ends are 'e', next level checks 'ed de'.
3. length 5 >= 2, both ends are 'e', next level checks 'd d'.
4. length 3 >= 2, both ends are 'd', next level checks ' ' (space).
5. length 1 <  2, return true.

В качестве альтернативы, непалиндром (хотя и мучительно близко), равный star rots, дает вам: 

1. length 9 >= 2, both ends are 's', next level checks 'tar rot'.
2. length 7 >= 2, both ends are 't', next level checks 'ar ro'.
3. length 5 >= 2, ends are 'a' and 'o', so return false.
...