computer science - Qu'est-ce que la récursivité et quand dois-je l'utiliser?

Translate

L'un des sujets qui semble revenir régulièrement sur les listes de diffusion et les discussions en ligne est le mérite (ou l'absence de diplôme) de faire un diplôme en informatique. Un argument qui semble revenir à maintes reprises pour la partie négative est qu'ils codent depuis un certain nombre d'années et qu'ils n'ont jamais utilisé la récursivité.

La question est donc:

  1. Qu'est-ce que la récursivité?
  2. Quand utiliserais-je la récursivité?
  3. Pourquoi les gens n'utilisent-ils pas la récursivité?
This question and all comments follow the "Attribution Required."

Toutes les réponses

Translate

Il existe un certain nombre de bonnes explicationsrécursivitédans ce fil, cette réponse explique pourquoi vous ne devriez pas l'utiliser dans la plupart des langages. * Dans la majorité des principales implémentations de langage impératif (c'est-à-dire toutes les implémentations majeures de C, C ++, Basic, Python, Ruby, Java et C #)itérationest largement préférable à la récursivité.

Pour comprendre pourquoi, suivez les étapes que les langues ci-dessus utilisent pour appeler une fonction:

  1. l'espace est taillé surla pilepour les arguments de la fonction et les variables locales
  2. les arguments de la fonction sont copiés dans ce nouvel espace
  3. la commande passe à la fonction
  4. le code de la fonction s'exécute
  5. le résultat de la fonction est copié dans une valeur de retour
  6. la pile est rembobinée à sa position précédente
  7. le contrôle revient à l'endroit où la fonction a été appelée

Effectuer toutes ces étapes prend du temps, généralement un peu plus qu'il n'en faut pour parcourir une boucle. Cependant, le vrai problème est à l'étape 1. Lorsque de nombreux programmes démarrent, ils allouent un seul morceau de mémoire pour leur pile, et lorsqu'ils sont à court de cette mémoire (souvent, mais pas toujours en raison de la récursivité), le programme se bloque en raison d'undébordement de pile.

Donc, dans ces langages, la récursivité est plus lente et vous rend vulnérable aux plantages. Il y a encore quelques arguments pour l'utiliser. En général, le code écrit récursivement est plus court et un peu plus élégant, une fois que vous savez le lire.

Il existe une technique que les développeurs de langage peuvent utiliser, appeléeoptimisation des appels de queuece qui peut éliminer certaines classes de débordement de pile. En bref: si l'expression de retour d'une fonction est simplement le résultat d'un appel de fonction, vous n'avez pas besoin d'ajouter un nouveau niveau à la pile, vous pouvez réutiliser celui en cours pour la fonction appelée. Malheureusement, peu d'implémentations impératives de langage ont une optimisation des appels de fin intégrée.

* J'adore la récursivité.Mon langage statique préférén'utilise pas du tout de boucles, la récursivité est le seul moyen de faire quelque chose de façon répétée. Je ne pense tout simplement pas que la récursivité soit généralement une bonne idée dans les langues qui ne sont pas adaptées.

** Au fait, Mario, le nom typique de votre fonction ArrangeString est "join", et je serais surpris si votre langue de choix n'en a pas déjà une implémentation.

La source
Translate

Exemple anglais simple de récursivité.

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
         ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.
La source
Sally Lee
Translate

Au sens le plus élémentaire de l'informatique, la récursivité est une fonction qui s'appelle elle-même. Supposons que vous ayez une structure de liste liée:

struct Node {
    Node* next;
};

Et vous voulez savoir combien de temps dure une liste liée, vous pouvez le faire avec la récursivité:

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(Cela pourrait bien sûr être fait avec une boucle for, mais est utile comme illustration du concept)

La source
Translate

Chaque fois qu'une fonction s'appelle elle-même, créant une boucle, alors c'est la récursivité. Comme pour tout, il y a de bons et de mauvais usages pour la récursivité.

L'exemple le plus simple est la récursivité de queue où la toute dernière ligne de la fonction est un appel à elle-même:

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

Cependant, c'est un exemple boiteux, presque inutile, car il peut facilement être remplacé par une itération plus efficace. Après tout, la récursivité souffre de la surcharge des appels de fonction, qui dans l'exemple ci-dessus pourrait être substantielle par rapport à l'opération à l'intérieur de la fonction elle-même.

Donc, la seule raison de faire de la récursion plutôt que de l'itération devrait être de tirer parti de lapile d'appelspour faire des trucs intelligents. Par exemple, si vous appelez une fonction plusieurs fois avec des paramètres différents dans la même boucle, c'est un moyen d'accomplirramification. Un exemple classique est leTriangle de Sierpinski.

enter image description here

Vous pouvez en dessiner un très simplement avec récursivité, où la pile d'appels se branche dans 3 directions:

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

Si vous essayez de faire la même chose avec l'itération, je pense que vous constaterez que cela prend beaucoup plus de code à accomplir.

D'autres cas d'utilisation courants peuvent inclure la traversée des hiérarchies, par exemple les robots d'exploration de sites Web, les comparaisons de répertoires, etc.

Conclusion

En termes pratiques, la récursivité a le plus de sens chaque fois que vous avez besoin d'un branchement itératif.

La source
Translate

La récursivité est une méthode de résolution de problèmes basée sur la mentalité de diviser pour conquérir. L'idée de base est de prendre le problème d'origine et de le diviser en instances plus petites (plus faciles à résoudre) de lui-même, de résoudre ces instances plus petites (généralement en utilisant à nouveau le même algorithme), puis de les rassembler dans la solution finale.

L'exemple canonique est une routine pour générer le factoriel de n. La factorielle de n est calculée en multipliant tous les nombres entre 1 et n. Une solution itérative en C # ressemble à ceci:

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

Il n'y a rien de surprenant à propos de la solution itérative et elle devrait avoir du sens pour quiconque connaît le C #.

La solution récursive est trouvée en reconnaissant que le nième Factoriel est n * Fact (n-1). Ou pour le dire autrement, si vous savez quel est un nombre factoriel particulier, vous pouvez calculer le suivant. Voici la solution récursive en C #:

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

La première partie de cette fonction est connue sous le nom deCas de base(ou parfois la clause de garde) et c'est ce qui empêche l'algorithme de s'exécuter pour toujours. Il renvoie simplement la valeur 1 chaque fois que la fonction est appelée avec une valeur de 1 ou moins. La deuxième partie est plus intéressante et est connue sous le nom deÉtape récursive. Ici, nous appelons la même méthode avec un paramètre légèrement modifié (nous le décrémentons de 1) puis multiplions le résultat par notre copie de n.

Lors de la première rencontre, cela peut être un peu déroutant, il est donc instructif d'examiner comment cela fonctionne lors de l'exécution. Imaginez que nous appelons FactRec (5). Nous entrons dans la routine, ne sommes pas pris en compte par le cas de base et nous finissons donc comme ceci:

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

Si nous réintroduisons la méthode avec le paramètre 4, nous ne sommes pas encore arrêtés par la clause de garde et nous aboutissons donc à:

// In FactRec(4)
return 4 * FactRec(3);

Si nous substituons cette valeur de retour dans la valeur de retour ci-dessus, nous obtenons

// In FactRec(5)
return 5 * (4 * FactRec(3));

Cela devrait vous donner un indice sur la façon dont la solution finale est arrivée, nous allons donc accélérer et montrer chaque étape en descendant:

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

Cette substitution finale se produit lorsque le cas de base est déclenché. À ce stade, nous avons une formule algébrique simple à résoudre qui équivaut directement à la définition des factorielles en premier lieu.

Il est instructif de noter que chaque appel dans la méthode entraîne le déclenchement d'un cas de base ou un appel à la même méthode où les paramètres sont plus proches d'un cas de base (souvent appelé appel récursif). Si ce n'est pas le cas, la méthode s'exécutera indéfiniment.

La source
Victoria Lee
Translate

La récursivité résout un problème avec une fonction qui s'appelle elle-même. Un bon exemple de ceci est une fonction factorielle. Factorielle est un problème mathématique où la factorielle de 5, par exemple, est 5 * 4 * 3 * 2 * 1. Cette fonction résout cela en C # pour les entiers positifs (non testé - il peut y avoir un bogue).

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}
La source
Norma Lee
Translate

La récursivité fait référence à une méthode qui résout un problème en résolvant une version plus petite du problème, puis en utilisant ce résultat plus un autre calcul pour formuler la réponse au problème d'origine. Souvent, lors du processus de résolution de la version la plus petite, la méthode résoudra une version encore plus petite du problème, et ainsi de suite, jusqu'à ce qu'elle atteigne un «cas de base» qui est facile à résoudre.

Par exemple, pour calculer une factorielle pour le nombreX, on peut le représenter commeX times the factorial of X-1. Ainsi, la méthode "se répète" pour trouver la factorielleX-1, puis multiplie tout ce qu'il a obtenuXpour donner une réponse finale. Bien sûr, pour trouver la factorielle deX-1, il calculera d'abord la factorielle deX-2, etc. Le cas de base serait quandXvaut 0 ou 1, auquel cas il sait retourner1depuis0! = 1! = 1.

La source
Eunice Lee
Translate

Considérez unvieux problème bien connu:

En mathématiques, leplus grand diviseur commun(pgcd)… de deux ou plusieurs entiers différents de zéro, est le plus grand entier positif qui divise les nombres sans reste.

La définition de pgcd est étonnamment simple:

gcd definition

où mod est leopérateur modulo(c'est-à-dire le reste après la division entière).

En anglais, cette définition dit que le plus grand diviseur commun de tout nombre et que zéro est ce nombre, et le plus grand diviseur commun de deux nombresmetnest le plus grand diviseur commun denet le reste après la divisionmparn.

Si vous souhaitez savoir pourquoi cela fonctionne, consultez l'article de Wikipédia sur leAlgorithme euclidien.

Calculons gcd (10, 8) comme exemple. Chaque pas est égal à celui juste avant:

  1. pgcd (10, 8)
  2. pgcd (10, 10 mod 8)
  3. pgcd (8, 2)
  4. pgcd (8, 8 mod 2)
  5. pgcd (2, 0)
  6. 2

Dans la première étape, 8 n'est pas égal à zéro, donc la deuxième partie de la définition s'applique. 10 mod 8 = 2 car 8 entre une fois dans 10 avec un reste de 2. A l'étape 3, la seconde partie s'applique à nouveau, mais cette fois 8 mod 2 = 0 car 2 divise 8 sans reste. À l'étape 5, le deuxième argument est 0, donc la réponse est 2.

Avez-vous remarqué que pgcd apparaît sur les côtés gauche et droit du signe égal? Un mathématicien dirait que cette définition est récursive car l'expression que vous définissezse répètedans sa définition.

Les définitions récursives ont tendance à être élégantes. Par exemple, une définition récursive pour la somme d'une liste est

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

headest le premier élément d'une liste ettailest le reste de la liste. Notez quesumrevient à l'intérieur de sa définition à la fin.

Peut-être préférez-vous plutôt la valeur maximale dans une liste:

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

Vous pouvez définir la multiplication d'entiers non négatifs de manière récursive pour en faire une série d'ajouts:

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

Si cela n'a pas de sens de transformer la multiplication en une série d'ajouts, essayez de développer quelques exemples simples pour voir comment cela fonctionne.

Tri par fusiona une belle définition récursive:

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

Les définitions récursives sont omniprésentes si vous savez ce qu'il faut rechercher. Remarquez comment toutes ces définitions ont des cas de base très simples,par exemple, pgcd (m, 0) = m. Les cas récursifs réduisent le problème pour arriver aux réponses faciles.

Avec cette compréhension, vous pouvez maintenant apprécier les autres algorithmes deArticle de Wikipedia sur la récursivité!

La source
Kama Lee
Translate
  1. Une fonction qui s'appelle
  2. Lorsqu'une fonction peut être (facilement) décomposée en une opération simple plus la même fonction sur une partie plus petite du problème. Je devrais plutôt dire que cela en fait un bon candidat pour la récursivité.
  3. Ils font!

L'exemple canonique est le factoriel qui ressemble à:

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

En général, la récursivité n'est pas nécessairement rapide (la surcharge des appels de fonction a tendance à être élevée car les fonctions récursives ont tendance à être petites, voir ci-dessus) et peuvent souffrir de certains problèmes (débordement de pile, n'importe qui?). Certains disent qu'ils ont tendance à être difficiles à «corriger» dans des cas non triviaux, mais je n'y adhère pas vraiment. Dans certaines situations, la récursivité a le plus de sens et est la manière la plus élégante et la plus claire d'écrire une fonction particulière. Il est à noter que certains langages favorisent les solutions récursives et les optimisent beaucoup plus (on pense à LISP).

La source
Beau Lee
Translate

Une fonction récursive est une fonction qui s'appelle elle-même. La raison la plus courante que j'ai trouvée pour l'utiliser est de traverser une structure arborescente. Par exemple, si j'ai un TreeView avec des cases à cocher (pensez à l'installation d'un nouveau programme, page "choisir les fonctionnalités à installer"), je pourrais vouloir un bouton "tout cocher" qui ressemblerait à ceci (pseudocode):

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

Vous pouvez donc voir que checkRecursively vérifie d'abord le nœud auquel il est passé, puis s'appelle lui-même pour chacun des enfants de ce nœud.

Vous devez être un peu prudent avec la récursivité. Si vous entrez dans une boucle récursive infinie, vous obtiendrez une exception Stack Overflow :)

Je ne peux pas penser à une raison pour laquelle les gens ne devraient pas l'utiliser, le cas échéant. Il est utile dans certaines circonstances et pas dans d'autres.

Je pense que parce que c'est une technique intéressante, certains codeurs finissent peut-être par l'utiliser plus souvent qu'ils ne le devraient, sans réelle justification. Cela a donné à la récursion un mauvais nom dans certains cercles.

La source
Freda Lee
Translate

La récursivité est une expression se référant directement ou indirectement à elle-même.

Considérez les acronymes récursifs comme un exemple simple:

  • GNOUsignifieGNU n'est pas Unix
  • PHPsignifiePHP: préprocesseur hypertexte
  • YAMLsignifieYAML n'est pas un langage de balisage
  • DU VINsignifieWine n'est pas un émulateur
  • VISAsignifieVisa International Service Association

Plus d'exemples sur Wikipedia

La source
Dorothy Lee
Translate

La récursivité fonctionne mieux avec ce que j'aime appeler des "problèmes fractals", où vous avez affaire à une grande chose qui est faite de versions plus petites de cette grande chose, dont chacune est une version encore plus petite de la grande chose, et ainsi de suite. Si jamais vous devez traverser ou rechercher quelque chose comme un arbre ou des structures identiques imbriquées, vous avez un problème qui pourrait être un bon candidat pour la récursivité.

Les gens évitent la récursivité pour plusieurs raisons:

  1. La plupart des gens (moi y compris) ont fait leurs preuves en programmation sur la programmation procédurale ou orientée objet par opposition à la programmation fonctionnelle. Pour ces personnes, l'approche itérative (utilisant généralement des boucles) semble plus naturelle.

  2. Ceux d'entre nous qui se sont fait les dents en programmation sur la programmation procédurale ou orientée objet ont souvent été invités à éviter la récursivité car elle est sujette aux erreurs.

  3. On nous dit souvent que la récursivité est lente. L'appel et le retour d'une routine impliquent à plusieurs reprises beaucoup de poussées et de sauts de pile, ce qui est plus lent que la boucle. Je pense que certains langages gèrent mieux cela que d'autres, et ces langages ne sont probablement pas ceux où le paradigme dominant est procédural ou orienté objet.

  4. Pour au moins quelques langages de programmation que j'ai utilisés, je me souviens avoir entendu des recommandations de ne pas utiliser la récursivité si elle dépasse une certaine profondeur parce que sa pile n'est pas si profonde.

La source
May Lee
Translate

Une instruction récursive est une instruction dans laquelle vous définissez le processus de ce qu'il faut faire ensuite comme une combinaison des entrées et de ce que vous avez déjà fait.

Par exemple, prenez factorielle:

factorial(6) = 6*5*4*3*2*1

Mais il est facile de voir factoriel (6) est aussi:

6 * factorial(5) = 6*(5*4*3*2*1).

Donc généralement:

factorial(n) = n*factorial(n-1)

Bien sûr, le problème avec la récursivité est que si vous voulez définir les choses en fonction de ce que vous avez déjà fait, il doit y avoir un point de départ.

Dans cet exemple, nous faisons juste un cas particulier en définissant factoriel (1) = 1.

Maintenant, nous le voyons de bas en haut:

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

Puisque nous avons défini factoriel (1) = 1, nous atteignons le «bas».

De manière générale, les procédures récursives comportent deux parties:

1) La partie récursive, qui définit une procédure en termes de nouvelles entrées combinées avec ce que vous avez "déjà fait" via la même procédure. (c'est à direfactorial(n) = n*factorial(n-1))

2) Une partie de base, qui s'assure que le processus ne se répète pas éternellement en lui donnant un endroit pour commencerfactorial(1) = 1)

Il peut être un peu déroutant de comprendre au début, mais il suffit de regarder un tas d'exemples et tout devrait être réuni. Si vous voulez une compréhension beaucoup plus profonde du concept, étudiez l'induction mathématique. Sachez également que certains langages sont optimisés pour les appels récursifs tandis que d'autres ne le font pas. Il est assez facile de créer des fonctions récursives incroyablement lentes si vous ne faites pas attention, mais il existe également des techniques pour les rendre performantes dans la plupart des cas.

J'espère que cela t'aides...

La source
Odelia Lee
Translate

J'aime cette définition:
En récursivité, une routine résout elle-même une petite partie d'un problème, divise le problème en parties plus petites, puis s'appelle elle-même pour résoudre chacune des parties plus petites.

J'aime aussi la discussion de Steve McConnells sur la récursivité dans Code Complete où il critique les exemples utilisés dans les livres d'informatique sur la récursivité.

N'utilisez pas de récursivité pour les factorielles ou les nombres de Fibonacci

Un problème avec les manuels d'informatique est qu'ils présentent des exemples idiots de récursivité. Les exemples typiques sont le calcul d'une factorielle ou le calcul d'une séquence de Fibonacci. La récursivité est un outil puissant et il est vraiment stupide de l'utiliser dans l'un ou l'autre de ces cas. Si un programmeur qui travaillait pour moi utilisait la récursivité pour calculer une factorielle, j'embaucherais quelqu'un d'autre.

J'ai pensé que c'était un point très intéressant à soulever et que cela pourrait expliquer pourquoi la récursivité est souvent mal comprise.

EDIT: Ce n'était pas une fouille à la réponse de Dav - je n'avais pas vu cette réponse quand j'ai posté ceci

La source
Translate

1.) Une méthode est récursive si elle peut s'appeler elle-même; soit directement:

void f() {
   ... f() ... 
}

ou indirectement:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) Quand utiliser la récursivité

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) Les gens n'utilisent la récursivité que lorsqu'il est très complexe d'écrire du code itératif. Par exemple, les techniques de traversée d'arbres telles que le pré-ordre, le post-ordre peuvent être à la fois itératives et récursives. Mais généralement, nous utilisons récursif en raison de sa simplicité.

La source
Translate

Voici un exemple simple: combien d'éléments dans un ensemble. (il existe de meilleures façons de compter les choses, mais c'est un bel exemple récursif simple.)

Premièrement, nous avons besoin de deux règles:

  1. si l'ensemble est vide, le nombre d'éléments dans l'ensemble est nul (duh!).
  2. si l'ensemble n'est pas vide, le nombre est égal à un plus le nombre d'éléments de l'ensemble après la suppression d'un élément.

Supposons que vous ayez un ensemble comme celui-ci: [xxx]. comptons combien il y a d'articles.

  1. l'ensemble est [xxx] ce qui n'est pas vide, donc nous appliquons la règle 2. le nombre d'éléments est un plus le nombre d'éléments dans [xx] (c'est-à-dire que nous avons supprimé un élément).
  2. l'ensemble est [xx], nous appliquons donc à nouveau la règle 2: un + nombre d'éléments dans [x].
  3. l'ensemble est [x], ce qui correspond toujours à la règle 2: un + nombre d'éléments dans [].
  4. Maintenant, l'ensemble est [], ce qui correspond à la règle 1: le compte est nul!
  5. Maintenant que nous connaissons la réponse à l'étape 4 (0), nous pouvons résoudre l'étape 3 (1 + 0)
  6. De même, maintenant que nous connaissons la réponse à l'étape 3 (1), nous pouvons résoudre l'étape 2 (1 + 1)
  7. Et enfin, maintenant que nous connaissons la réponse à l'étape 2 (2), nous pouvons résoudre l'étape 1 (1 + 2) et obtenir le nombre d'éléments dans [xxx], qui est de 3. Hourra!

Nous pouvons représenter cela comme:

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

Lors de l'application d'une solution récursive, vous avez généralement au moins 2 règles:

  • la base, le cas simple qui énonce ce qui se passe lorsque vous avez «épuisé» toutes vos données. Il s'agit généralement d'une variante de "si vous n'avez plus de données à traiter, votre réponse est X"
  • la règle récursive, qui indique ce qui se passe si vous avez encore des données. Il s'agit généralement d'une sorte de règle qui dit «faites quelque chose pour réduire votre ensemble de données et réappliquez vos règles au plus petit ensemble de données».

Si nous traduisons ce qui précède en pseudocode, nous obtenons:

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

Il y a beaucoup plus d'exemples utiles (traversant un arbre, par exemple) que je suis sûr que d'autres personnes couvriront.

La source
Bblythe Lee
Translate

Eh bien, c'est une définition assez décente que vous avez. Et wikipedia a aussi une bonne définition. Je vais donc ajouter une autre définition (probablement pire) pour vous.

Quand les gens parlent de «récursion», ils parlent généralement d'une fonction qu'ils ont écrite et qui s'appelle elle-même à plusieurs reprises jusqu'à ce qu'elle en ait terminé avec son travail. La récursivité peut être utile lors de la traversée des hiérarchies dans les structures de données.

La source
Wordsworth Lee
Translate

Un exemple: Une définition récursive d'un escalier est: Un escalier se compose de: - une seule marche et un escalier (récursivité) - ou seulement une seule marche (terminaison)

La source
Corey Lee
Translate

Pour revenir sur un problème résolu: ne faites rien, vous avez terminé.
Pour récidiver sur un problème ouvert: passez à l'étape suivante, puis récidivez sur le reste.

La source
Alvin Lee
Translate

En clair: Supposons que vous puissiez faire 3 choses:

  1. Prends une pomme
  2. Notez les marques de pointage
  3. Compter les marques de pointage

Vous avez beaucoup de pommes devant vous sur une table et vous voulez savoir combien il y a de pommes.

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

Le processus consistant à répéter la même chose jusqu'à ce que vous ayez terminé s'appelle la récursivité.

J'espère que c'est la réponse "en clair" que vous recherchez!

La source
Daniel Lee
Translate

Une fonction récursive est une fonction qui contient un appel à elle-même. Une structure récursive est une structure qui contient une instance d'elle-même. Vous pouvez combiner les deux en tant que classe récursive. L'élément clé d'un élément récursif est qu'il contient une instance / un appel de lui-même.

Considérez deux miroirs face à face. Nous avons vu l'effet infini qu'ils produisent. Chaque réflexion est une instance d'un miroir, qui est contenue dans une autre instance d'un miroir, etc. Le miroir contenant un reflet de lui-même est la récursivité.

A arbre de recherche binaireest un bon exemple de programmation de récursivité. La structure est récursive avec chaque Node contenant 2 instances d'un Node. Les fonctions permettant de travailler sur un arbre de recherche binaire sont également récursives.

La source
Gloria Lee
Translate

C'est une vieille question, mais je veux ajouter une réponse du point de vue logistique (c'est-à-dire pas du point de vue de l'exactitude de l'algorithme ou du point de vue des performances).

J'utilise Java pour le travail et Java ne prend pas en charge les fonctions imbriquées. En tant que tel, si je veux faire de la récursivité, je pourrais avoir à définir une fonction externe (qui n'existe que parce que mon code se heurte à la règle bureaucratique de Java), ou je pourrais avoir à refactoriser le code complètement (ce que je déteste vraiment faire).

Ainsi, j'évite souvent la récursivité et j'utilise plutôt une opération de pile, car la récursivité elle-même est essentiellement une opération de pile.

La source
Ben Lee
Translate

Vous souhaitez l'utiliser à chaque fois que vous avez une structure arborescente. C'est très utile pour lire du XML.

La source
Nina Lee
Translate

La récursivité telle qu'elle s'applique à la programmation consiste essentiellement à appeler une fonction de l'intérieur de sa propre définition (à l'intérieur d'elle-même), avec différents paramètres afin d'accomplir une tâche.

La source
Pearl Lee
Translate

"Si j'ai un marteau, fais que tout ressemble à un clou."

La récursivité est une stratégie de résolution de problèmes pourénormeproblèmes, où à chaque étape, "transformez 2 petites choses en une seule chose plus grande", à chaque fois avec le même marteau.

Exemple

Supposons que votre bureau soit couvert d'un désordre désorganisé de 1024 papiers. Comment faire une pile de papiers ordonnée et propre à partir du désordre, en utilisant la récursivité?

  1. Diviser:Répartissez toutes les feuilles, de sorte que vous n'avez qu'une seule feuille dans chaque "pile".
  2. Conquérir:
    1. Faites le tour, en plaçant chaque feuille sur une autre feuille. Vous avez maintenant des piles de 2.
    2. Faites le tour, en plaçant chaque 2-stack au-dessus d'un autre 2-stack. Vous avez maintenant des piles de 4.
    3. Faites le tour, en plaçant chaque pile 4 sur une autre pile 4. Vous avez maintenant des piles de 8.
    4. ... encore et encore ...
    5. Vous avez maintenant une énorme pile de 1024 feuilles!

Notez que c'est assez intuitif, mis à part tout compter (ce qui n'est pas strictement nécessaire). Vous ne pouvez peut-être pas descendre jusqu'à des piles d'une feuille, en réalité, mais vous pourriez et cela fonctionnerait toujours. La partie importante est le marteau: avec vos bras, vous pouvez toujours mettre une pile au-dessus de l'autre pour faire une pile plus grande, et peu importe (dans des limites raisonnables) la taille de l'une ou l'autre pile.

La source
King Lee
Translate

La récursivité est le processus par lequel une méthode s'appelle soi-même pour pouvoir effectuer une certaine tâche. Cela réduit la redondance du code. La plupart des fonctions ou méthodes récursives doivent avoir une condition pour interrompre l'appel récurrent, c'est-à-dire l'empêcher de s'appeler si une condition est remplie - cela empêche la création d'une boucle infinie. Toutes les fonctions ne sont pas adaptées pour être utilisées de manière récursive.

La source
Vicky Lee
Translate

hé, désolé si mon avis est d'accord avec quelqu'un, j'essaie juste d'expliquer la récursivité en anglais simple.

supposons que vous ayez trois managers - Jack, John et Morgan. Jack gère 2 programmeurs, John - 3 et Morgan - 5. vous allez donner à chaque manager 300 $ et vous voulez savoir ce que cela coûterait. La réponse est évidente - mais que se passe-t-il si 2 des employés de Morgan sont également des managers?

ICI vient la récursion. vous partez du haut de la hiérarchie. le coût estival est de 0 $. vous commencez par Jack, puis vérifiez s'il a des managers comme employés. si vous trouvez que l'un d'entre eux le sont, vérifiez s'ils ont des gestionnaires comme employés et ainsi de suite. Ajoutez 300 $ au coût estival chaque fois que vous trouvez un gestionnaire. quand vous en aurez fini avec Jack, allez voir John, ses employés et ensuite Morgan.

Vous ne saurez jamais combien de cycles allez-vous parcourir avant d'obtenir une réponse, même si vous savez combien de gestionnaires vous avez et combien de budget pouvez-vous dépenser.

La récursivité est un arbre, avec des branches et des feuilles, appelés respectivement parents et enfants. Lorsque vous utilisez un algorithme de récursivité, vous construisez plus ou moins consciemment une arborescence à partir des données.

La source
Betty Lee
Translate

En anglais simple, récursivité signifie répéter quelque chose encore et encore.

En programmation, un exemple est d'appeler la fonction en elle-même.

Regardez l'exemple suivant de calcul factoriel d'un nombre:

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}
La source
Roy Lee
Translate

Tout algorithme exposede constructionrécursivité sur un type de données si consiste essentiellement en une instruction switch avec un cas pour chaque cas du type de données.

par exemple, lorsque vous travaillez sur un type

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

un algorithme structurel récursif aurait la forme

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

c'est vraiment la manière la plus évidente d'écrire un algorithme qui fonctionne sur une structure de données.

maintenant, quand vous regardez les entiers (enfin, les nombres naturels) tels que définis à l'aide des axiomes Peano

 integer = 0 | succ(integer)

vous voyez qu'un algorithme structurel récursif sur les entiers ressemble à ceci

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

la fonction factorielle trop connue est à peu près l'exemple le plus trivial de cette forme.

La source
Shirley Lee
Translate

la fonction s'appelle elle-même ou utilise sa propre définition.

La source