Résumé de la récurrence Java

J'ai besoin d'une personne de classe pour décrire les personnes. Chaque personne a un nom et un tableau composé d'objets Personne, qui représentent les enfants de la personne. La classe de personne a une méthode getNumberOfDescendants, qui renvoie un nombre entier égal au nombre total de descendants de la personne, c'est-à-dire ses enfants plus petits-enfants plus leurs enfants etc. Existe-t-il un moyen simple d'utiliser la récursivité?Résumé de la récurrence Java

Que faire si vous voulez compter les descendants d'une certaine génération seulement? En d'autres termes, getNumberOfDescendants (génération int) retournera le nombre d'enfants si la génération = 1, le nombre de petits-enfants si la génération = 2, etc.

Source

2009-11-30 rize

Ce Smells comme quelque chose qui devrait être étiqueté « devoirs ». –

il y avait une étiquette « odeurs comme-devoirs » pour que .. –

Non, non, il n'y a rien à voir avec l'exercice du cours: D En tout cas, je me demande, quelle est la différence exacte entre « itération » et « récursivité » ? Je pense que c'est récursif, quand vous appelez une méthode à l'intérieur de lui-même, comme dans les solutions d'échantillon, mais l'itération est "pour, alors", etc. Je suppose qu'il n'y a pas de solution purement récursive? Autrement dit, une solution qui n'utilise pas la boucle for? – rize

Bien sûr.

public class Person { 

private Person[] myChildren; 

public int getNumberOfDescendants() { 
    if (myChildren == null || myChildren.length==0) return 0; 
    int myDescendants = 0; 
    for (Person child:myChildren) { 
    myDescendants += 1; // for this particular child itself 
    myDescendants += child.getNumberOfDescendants(); //add the child's children, grandchildren, etc. 
    } 
    return myDescendants; 
} 

}

Source

2009-11-30 19:34:50

Notez que les deux lignes qui font l'incrémentation pourraient facilement être remplacées par une seule ligne "myChildren + = 1 + child.getNumberOfDescendants();". Je l'ai fait en deux lignes pour la clarté et la facilité de commenter. –

Oui, c'est ainsi que je l'ai finalement écrit. Quoi qu'il en soit, merci par exemple, maintenant j'ai eu le coup de la récursion dans ce domaine. – rize

Vous savez que cela ne compile pas correctement? –

getNumberOfDescendants() 
{ 
    int sum = 0; 
    for (int n=0; n < descendants.length; n++) 
    { 
    sum += 1 + descendants[n].getNumberOfDescendants(); 
    } 
    return sum; 
}

Notez que le « 1 + » est le seul endroit où nous » re augmente réellement le nombre. Cette ligne est appelée une fois pour chaque descendant de l'arbre.

Source

2009-11-30 19:33:41

Seul le problème ici est l'hypothèse que le tableau des descendants ne sera jamais nul. –

Vrai ... Je pense que je pensais en termes de collections où même un vide aura toujours un objet alloué que vous pouvez traverser (0 fois). Java autorise-t-il les tableaux de longueur nulle? –

Oui, le tableau peut exister mais avoir une longueur nulle, auquel cas votre code fonctionnera. –

Ce n'est pas vraiment récursion, en soi, mais une instance de la classe pourrait résumer les résultats de l'appel de la méthode getNumberOfDescendants() pour chacun de ses enfants.

Sinon, vous pouvez rendre cette méthode plus rapide en ayant chaque instance notifie son parent chaque fois qu'il a obtenu un nouveau descendant (soit un nouvel enfant ou d'être informé par un enfant). De cette façon, son compte du nombre de descendants serait toujours à jour.

Source

2009-11-30 19:37:37

public int getNumberDescendents() 
    { 
    int nDesc = 0; 
    if (descendants != null) 
    { 
     for (Person p : descendants) 
     { 
     nDesc++; // this child 
     nDesc += p.getNumberDescendents(); // this child's desc 
     } 
    } 
    return nDesc; 
    }

Au moment où je l'ai écrit l'exemple en, d'autres avaient affiché fondamentalement la même chose, donc je suis un peu l'affichage de manière redondante.

Source

2009-11-30 19:56:27 PaulP1975

Si vous placez 4 espaces au début de chaque ligne, le code sera placé dans un joli bloc de code formaté. –

Merci pour le conseil Nate et pour l'édition JacobM! – PaulP1975

Résumé de la récurrence Java

Répondre

Questions connexes