Comment récursive isPalindrome fonction de travail?

Je travaille sur certains d'introduction les problèmes de la récursivité et j'ai une question de clarification, j'aimerais obtenir une réponse. La plus lancinante question que je me pose est de savoir comment est cette récursivité d'exploitation dans la solution du problème ci-dessous?

Malgré le fait d'avoir résolu le problème, je suis juste de ne pas comprendre comment la récursivité appel fait son chemin à l'intérieur de la chaîne. Il semblerait, de simplement en regardant le code, que cette méthode ne voulut jamais vérifier les deux personnages sur chaque extrémité de la chaîne, sans vérifier le reste. Mon manuel donne à l'profondément insatisfaisant réponse, en gros, ne vous inquiétez pas sur la façon de récursivité fonctionne tant que votre demande de retour affine le problème. Mais je vais avoir de la difficulté à savoir comment l'approche ultérieure problèmes de la récursivité, sans comprendre comment on peut trouver la trace d'une méthode récursive de la même manière on pourrait tracer une boucle.

Tous les mots de la sagesse serait très apprécié.

Merci!

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"));
}
}

OriginalL'auteur gryb | 2012-02-02

10

La isPalindrome() la fonction est récursive d'être appelé str.substring(1, str.longueur() -1). Donc, la pile devrait ressembler à ceci pour le isPalindrome() appelle:
```
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
```
La valeur de retour du dernier appel de propagation de tous les chemin vers le haut.

Avec la récursivité, des photos toujours de l'aide. Faites de votre mieux pour tirer la pile des appels sous forme de diagramme. Il va vous permettre de visualiser et donc de mieux comprendre, de plus en plus complexe récurrences. C'est un simple "linéaire" de la récursivité, mais vous pourrez éventuellement faire face à "l'arbre" comme récurrences.

Voici une photo qui illustre bien ce problème exact pour vous permettre de mieux visualiser:

Merci le diagramme a été très utile, je pense que je commence à saisir le concept.
pas de soucis, une fois que vous prenez le concept, ça deviendra plus facile de comprendre les autres algorithmes récursifs =D

OriginalL'auteur Nadir Muzaffar

Penser le palindrome:

risetovotesir

Cet état de fait peut être construit par partir avec le palindrome v (une chaîne de caractères est toujours un palindrome, comme c'est une chaîne vide) et en ajoutant la même lettre à l'avant et à l'arrière:

      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'.

Le processus utilisé par la fonction récursive est dans la direction opposée, la rupture de la chaîne de bits par bits. Il détecte si c'est un palindrome est si à la fois:

les premiers et derniers caractères sont égaux; et
l'intérieur de la chaîne (une fois que ces deux sont supprimés) est un palindrome.

D'où le code peut être écrit comme:

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));
}

L'aide d'une chaîne de peed deep, les différents niveaux sont les suivants:

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.

Sinon, un non-palindrome (bien que la portée de proximité) de star rots vous donne:

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.

OriginalL'auteur paxdiablo

Vous devez vous connecter pour publier un commentaire.