Une question théorique ici à propos de la base ou de la casse d'arrêt dans une méthode récursive, quelles sont ses normes?
Je veux dire, est-il normal de ne pas avoir de corps dedans, juste une déclaration retourner ? est-il toujours comme ce qui suit: Avez-vous des idées différentes à ce sujet?
4 Réponses :
Le boîtier de base consiste à terminer la boucle (évitez de devenir une récursion infinie). Il n'y a pas de norme dans le boîtier de base, toute entrée suffisamment simple pour être résolue exactement peut être choisie exactement comme une.
Par exemple, cela est parfaitement valide: P>
int factorial (int n) {
if (n <= 5) {
// Not just a return statement
int x = 1;
while (n > 0) {
x *= n;
-- n;
}
return x;
} else {
return n * factorial(n-1);
}
}
J'ai dit que je pose une question théorique, je veux dire si je veux enseigner à la récursion, je ne sais pas votre code précédent, je sais que c'est une manière valide, mais cela ne fait pas de récursion et le concept de cas de base suffisamment clair, que penses-tu?
Le modèle pour des fonctions récursives est qu'ils ressemblent à ceci comme suit:
f( value )
if ( test value )
return value
else
return f( simplify value )
Quel langage de programmation est-ce?
@Solace qui ressemble plus à un pseudocode, pas de langage de programmation particulier
C'est de loin le meilleur moyen d'expliquer les méthodes récursives. J'ai utilisé cette approche pour la fusion de deux lignes de mise en œuvre de la liste liée.
Cela dépend entièrement de la fonction récursive particulière. En général, il ne peut pas être un retour vide; , cependant - pour toute fonction récursive qui renvoie une valeur, le boîtier de base doit également renvoyer une valeur de ce type, puisque Func ( base) est également un appel parfaitement valide. Par exemple, une fonction RÉCURSIVE FACTORIAL retournerait un 1 comme valeur de base.
Une méthode récursive n'a pas à renvoyer une valeur, cependant.
Vrai, bien sûr. Mais alors, je pouvais dire: pour des méthodes récursives qui renvoient void , la base retournera également vide ...;)
Dans certains cas, votre cas de base est Dans certains cas, votre cas de base n'est pas simplement "renvoyer un littéral". Il ne peut pas y avoir de " Standard »- cela dépend de votre fonction. la "Fonction Syracuse" http://fr.wikipedia.org/wiki/ Collatz_Conjecture par exemple,
n'a pas de cas de base trivial ou une valeur littérale triviale. "Avez-vous des idées différentes à ce sujet ??" N'est pas vraiment une question raisonnable. La récursion doit terminer, c'est tout. Une récursion de queue triviale peut avoir un "cas de base" qui retourne un littéral, ou peut être un calcul. Une récursion plus complexe peut ne pas avoir de "cas de base" trivial.
En essayant de développer plus loin sur cette réponse, un cas de base dans une fonction récursive pourrait également être quelque chose dont O (n) est sensiblement inférieur au O (n) de la réelle fonction. D'accord renvoyant une opération plus simple (moins complexe).