Qu’est-ce que la récursivité et quand devrais-je l’utiliser?

Un des sujets qui semble apparaître régulièrement sur les listes de diffusion et les discussions en ligne est le bien-fondé (ou l’absence de pertinence) d’un diplôme d’informatique. Un argument qui semble revenir sans cesse à 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é.

Donc la question est:

  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é?

Il y a un certain nombre de bonnes explications de la récursivité dans ce thread, cette réponse explique pourquoi vous ne devriez pas l’utiliser dans la plupart des langages. * Dans la plupart des principales implémentations de langage impératif (c.-à-d. , Ruby, Java et C #) itération est largement préférable à la récursivité.

Pour savoir pourquoi, parcourez les étapes que les langages ci-dessus utilisent pour appeler une fonction:

  1. l’espace est découpé dans la stack pour les arguments de la fonction et les variables locales
  2. les arguments de la fonction sont copiés dans ce nouvel espace
  3. le contrôle saute à 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 stack est rembobinée à sa position précédente
  7. le contrôle retourne à l’endroit où la fonction a été appelée

Faire toutes ces étapes prend du temps, généralement un peu plus que ce qui est nécessaire pour parcourir une boucle. Cependant, le véritable problème est à l’étape 1. Lorsque de nombreux programmes démarrent, ils allouent un seul bloc de mémoire pour leur stack et, lorsqu’ils sont épuisés (souvent, mais pas toujours en raison de la récursivité), le programme se bloque en raison d’un débordement de stack .

Donc, dans ces langues, la récursivité est plus lente et cela vous rend vulnérable aux crashs. Il rest cependant des 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 comment le lire.

Il existe une technique que les implémenteurs de langage peuvent utiliser, appelée optimisation des appels de queue, qui peut éliminer certaines classes de débordement de stack. 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’append un nouveau niveau à la stack, vous pouvez réutiliser le niveau actuel pour la fonction appelée. Malheureusement, peu d’implémentations de langage impératives ont intégré l’optimisation de l’appel.

* J’aime la récursivité. Mon langage statique préféré n’utilise pas de boucles du tout, la récursivité est le seul moyen de faire quelque chose à plusieurs resockets. Je ne pense pas que la récursivité soit généralement une bonne idée dans les langues qui ne sont pas adaptées pour cela.

** Au fait, Mario, le nom typique de votre fonction ArrangeSsortingng est “join”, et je serais surpris si votre langue de choix ne l’avait pas déjà implémentée.

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. 

Dans le sens le plus fondamental de l’informatique, la récursivité est une fonction qui s’appelle elle-même. Disons que vous avez une structure de liste liée:

 struct Node { Node* next; }; 

Et vous voulez savoir combien de temps une liste chaînée peut 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)

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

L’exemple le plus simple est la récursion de la 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, il s’agit d’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 de l’appel de fonction, qui dans l’exemple ci-dessus pourrait être importante par rapport à l’opération à l’intérieur de la fonction elle-même.

Donc, la raison d’être de la récursivité plutôt que de l’itération devrait être de tirer parti de la stack d’appels pour faire des choses intelligentes. Par exemple, si vous appelez une fonction plusieurs fois avec des parameters différents dans la même boucle, c’est une manière d’accomplir des twigments . Un exemple classique est le sortingangle Sierpinski .

entrer la description de l'image ici

Vous pouvez en dessiner un très simplement avec récursivité, où la stack d’appels se divise en 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 une itération, je pense que vous constaterez que cela demande beaucoup plus de code.

Parmi les autres cas d’utilisation courants, citons les hiérarchies de parcours, par exemple les robots d’exploration de sites Web, les comparaisons de répertoires, etc.

Conclusion

En termes pratiques, la récursivité est la plus logique lorsque vous avez besoin de twigments itératifs.

La récursivité est une méthode de résolution de problèmes basée sur la mentalité de division et de conquête. L’idée de base est de prendre le problème initial et de le diviser en instances plus petites (plus facilement résolues), de résoudre ces petites instances (généralement en utilisant le même algorithme) et de les rassembler dans la solution finale.

L’exemple canonique est une routine pour générer le Factorial de n. Le factoriel de n est calculé 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’ya rien de surprenant dans la solution itérative et cela devrait être logique pour quiconque est familier avec C #.

La solution récursive est trouvée en reconnaissant que le nième Factorial est n * Fact (n-1). Ou, pour le dire autrement, si vous savez quel nombre factoriel particulier, vous pouvez calculer le prochain. 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 appelée un cas de base (ou parfois une clause de protection) et empêche l'exécution de l'algorithme pour toujours. Il renvoie simplement la valeur 1 chaque fois que la fonction est appelée avec une valeur inférieure ou égale à 1. La deuxième partie est plus intéressante et s'appelle l' é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 avec notre copie de n.

Lors de la première utilisation, cela peut être source de confusion, il est donc intéressant d'examiner comment cela fonctionne lors de l'exécution. Imaginez que nous appelons FactRec (5). Nous entrons dans la routine, nous ne sums pas pris en compte par le scénario de base et nous nous retrouvons ainsi:

 // In FactRec(5) return 5 * FactRec( 5 - 1 ); // which is return 5 * FactRec(4); 

Si nous rentrons la méthode avec le paramètre 4, nous ne sums pas à nouveau arrêtés par la clause de garde et nous nous retrouvons donc à:

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

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

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

Cela devrait vous donner une idée de la manière dont la solution finale est obtenue. Nous allons donc accélérer et afficher chaque étape à la baisse:

 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èbre simple à résoudre qui correspond directement à la définition des factoriels en premier lieu.

Il est instructif de noter que chaque appel dans la méthode entraîne soit le déclenchement d'un cas de base, soit un appel à la même méthode où les parameters sont plus proches d'un cas de base (souvent appelé appel récursif). Si ce n'est pas le cas, la méthode fonctionnera pour toujours.

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

 public int Factorial(int n) { if (n <= 1) return 1; return n * Factorial(n - 1); } 
  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 la factorielle 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 (les appels de fonction ont tendance à être élevés parce que les fonctions récursives ont tendance à être petites, voir ci-dessus) et peuvent présenter certains problèmes (débordement de stack?). Certains disent qu’ils ont tendance à avoir du mal à «bien se comporter» dans des cas non sortingviaux, mais je n’adhère pas vraiment à cela. Dans certaines situations, la récursivité est la plus logique et constitue la manière la plus élégante et la plus claire d’écrire une fonction particulière. Il convient de noter que certaines langues favorisent les solutions récursives et les optimisent beaucoup plus (en pensant à LISP).

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, au cours de la résolution de la version plus petite, la méthode résout une version encore plus petite du problème, et ainsi de suite, jusqu’à ce qu’il atteigne un “cas de base” qui est sortingvial à résoudre.

Par exemple, pour calculer une factorielle pour le nombre X , on peut la représenter comme X times the factorial of X-1 . Ainsi, la méthode “recurses” permet de trouver la factorielle de X-1 , puis multiplie ce qu’elle a obtenu par X pour donner une réponse finale. Bien sûr, pour trouver la factorielle de X-1 , il faudra d’abord calculer la factorielle de X-2 , et ainsi de suite. Le cas de base serait quand X est 0 ou 1, auquel cas il sait renvoyer 1 depuis 0! = 1! = 1 0! = 1! = 1 0! = 1! = 1 .

Considérons un vieux problème bien connu :

En mathématiques, le plus grand diviseur commun (gcd)… de deux entiers non nuls ou plus est le plus grand nombre entier positif qui divise les nombres sans rest.

La définition de gcd est étonnamment simple:

définition gcd

où mod est l’ opérateur modulo (c’est-à-dire le rest après la division entière).

En anglais, cette définition dit que le plus grand commun diviseur de n’importe quel nombre et zéro est ce nombre, et le plus grand commun diviseur de deux nombres m et n est le plus grand diviseur commun de n et le rest après la division de m .

Si vous souhaitez savoir pourquoi cela fonctionne, consultez l’article de Wikipedia sur l’ algorithme euclidien .

Calculons gcd (10, 8) comme exemple. Chaque pas est égal à celui qui précède:

  1. gcd (10, 8)
  2. gcd (10, 10 mod 8)
  3. gcd (8, 2)
  4. gcd (8, 8 mod 2)
  5. gcd (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 passe à 10 une fois avec un rest de 2. A l’étape 3, la deuxième partie s’applique à nouveau, mais cette fois 8 mod 2 = 0 car 2 divise 8 sans rest. A l’étape 5, le deuxième argument est 0, donc la réponse est 2.

Avez-vous remarqué que gcd apparaît à gauche et à droite du signe égal? Un mathématicien dirait que cette définition est récursive car l’expression que vous définissez est récurrente dans sa définition.

Les définitions récursives ont tendance à être élégantes. Par exemple, une définition récursive de la sum d’une liste est

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

head est le premier élément d’une liste et tail est le rest de la liste. Notez que la sum revient dans sa définition à la fin.

Peut-être préféreriez-vous la valeur maximale dans une liste à la place:

 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 en ce qui concerne la transformation de la multiplication en une série d’ajouts, essayez d’étendre quelques exemples simples pour voir comment cela fonctionne.

Fusionner le sorting a 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 partout si vous savez quoi chercher. Notez que toutes ces définitions ont des cas de base très simples, par exemple , gcd (m, 0) = m. Les cas récursifs minimisent le problème pour en arriver aux réponses faciles.

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

Une fonction récursive est celle qui s’appelle elle-même. La raison la plus courante pour laquelle je l’ai trouvé est la traversée d’une arborescence. 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 souhaiterais peut-être un bouton “vérifier tout” qui pourrait ressembler à 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 pour chacun des enfants de ce nœud.

Vous devez faire attention à 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. C’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écursivité un mauvais nom dans certains milieux.

La récursivité fonctionne mieux avec ce que j’appelle les “problèmes fractals”, où vous avez affaire à une grande chose faite de petites versions de cette grande chose, chacune étant une version encore plus petite, et ainsi de suite. Si vous devez parcourir ou parcourir quelque chose comme un arbre ou des structures identiques nestedes, 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 (y compris moi-même) ont réduit leur programmation en matière de programmation procédurale ou orientée object, par opposition à la functional programming. Pour ces personnes, l’approche itérative (généralement en utilisant des boucles) semble plus naturelle.

  2. On a souvent dit à ceux d’entre nous d’avoir recours à la programmation procédurale ou à la programmation orientée object pour é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 à maintes resockets une poussée et un éclatement de la stack, ce qui est plus lent que le bouclage. Je pense que certaines langues traitent cela mieux que d’autres, et ces langues ne sont probablement pas celles où le paradigme dominant est procédural ou orienté object.

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

La récursivité est une expression se référant directement ou indirectement.

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

  • GNU signifie GNU’s Not Unix
  • PHP signifie PHP: préprocesseur hypertexte
  • YAML signifie YAML Ain’t Markup Language
  • WINE signifie que le vin n’est pas un émulateur
  • VISA signifie Visa International Service Association

Plus d’exemples sur Wikipedia

Voici un exemple simple: combien d’éléments dans un ensemble. (il existe de meilleures façons de compter les choses, mais il s’agit d’un exemple simple et récursif.)

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 le jeu n’est pas vide, le compte est égal à un plus le nombre d’éléments dans l’ensemble après la suppression d’un élément.

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

  1. l’ensemble est [xxx] qui n’est pas vide, nous appliquons donc 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], qui correspond toujours à la règle 2: un + nombre d’éléments dans [].
  4. Maintenant, le jeu est [], ce qui correspond à la règle 1: le compte est zéro!
  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 3. Hourra!

Nous pouvons représenter cela comme:

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

Lorsque vous appliquez une solution récursive, vous avez généralement au moins 2 règles:

  • la base, le cas simple qui indique ce qui se passe lorsque vous avez “épuisé” toutes vos données. C’est généralement une variation de “si vous êtes à court 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 la taille de votre jeu de données et réappliquez vos règles au plus petit dataset».

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 d’autres exemples utiles (en traversant un arbre, par exemple) que d’autres personnes couvriront, j’en suis sûr.

Une déclaration récursive est une déclaration dans laquelle vous définissez le processus à suivre en tant que combinaison des entrées et de ce que vous avez déjà fait.

Par exemple, prenez factoriel:

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

Mais il est facile de voir que factorial (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, la récursivité est une chose délicate: si vous voulez définir des choses en fonction de ce que vous avez déjà fait, il faut un endroit où commencer.

Dans cet exemple, nous faisons simplement un cas particulier en définissant factorial (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 factorial (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. (ie factorial(n) = n*factorial(n-1) )

2) Une partie de base, qui garantit que le processus ne se répète pas pour toujours en lui donnant un endroit pour commencer (ie factorial(1) = 1 )

Il peut être un peu déroutant de commencer par vous pencher, mais il suffit de regarder un tas d’exemples et tout cela devrait s’unir. Si vous voulez une compréhension beaucoup plus approfondie du concept, étudiez l’induction mathématique. Sachez également que certaines langues optimisent les appels récursifs, alors que d’autres ne le font pas. Il est assez facile de faire 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…

J’aime cette définition:
En récursivité, une routine résout une petite partie du problème lui-même, divise le problème en petits morceaux, puis s’appelle pour résoudre chacun des plus petits morceaux.

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

Ne pas utiliser la récursivité pour les factorielles ou les nombres de Fibonacci

L’un des problèmes des manuels d’informatique est qu’ils présentent des exemples stupides 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 idiot de l’utiliser dans ces deux cas. Si un programmeur qui travaillait pour moi utilisait la récursivité pour calculer une factorielle, j’engagerais quelqu’un d’autre.

Je pensais que c’était un point très intéressant à soulever et peut être une raison pour laquelle 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é cette

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 personnes utilisent la récursivité uniquement lorsqu’il est très complexe d’écrire du code itératif. Par exemple, des techniques de traversée d’arbres telles que le précommande, le post-ordre peuvent être rendues à la fois itératives et récursives. Mais généralement, nous utilisons récursive en raison de sa simplicité.

S’en remettre à un problème résolu: ne faites rien, vous avez terminé.
S’en remettre à un problème ouvert: faites l’étape suivante, puis rentrez sur le rest.

Eh bien, c’est une définition assez décente que vous avez. Et wikipedia a aussi une bonne définition. Donc, je vais append une autre définition (probablement pire) pour vous.

Lorsque les gens se réfèrent à la “récursivité”, ils parlent généralement d’une fonction qu’ils ont écrite et qui se répète jusqu’à ce qu’elle soit terminée. La récursivité peut être utile lors du déplacement de hiérarchies dans des structures de données.

Un exemple: Une définition récursive d’un escalier est la suivante: Un escalier se compose de: – une marche et un escalier (récursivité) – ou une seule marche (terminaison)

En clair anglais: Supposons que vous puissiez faire 3 choses:

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

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

 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 de répétition de la même chose jusqu’à ce que vous ayez terminé s’appelle la récursivité.

J’espère que c’est la réponse “simple anglais” que vous recherchez!

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. La partie clé d’un élément récursif est qu’il contient une instance / un appel de lui-même.

Considérez deux miroirs qui se font face. Nous avons vu l’effet infini net qu’ils font. Chaque reflection 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 une récursivité.

Un arbre de recherche binary est un bon exemple de programmation de la récursivité. La structure est récursive avec chaque nœud contenant 2 instances d’un nœud. Les fonctions permettant de travailler sur un arbre de recherche binary sont également récursives.

C’est une vieille question, mais je veux append une réponse du sharepoint vue logistique (c.-à-d. Pas du sharepoint vue de l’exactitude de l’algorithme ou du sharepoint vue de la performance).

J’utilise Java pour travailler et Java ne supporte pas les fonctions nestedes. En tant que tel, si je veux faire de la récursivité, il se peut que je doive définir une fonction externe (qui existe uniquement parce que mon code est gêné par la règle bureaucratique de Java).

Par conséquent, j’évite souvent la récursivité et utilise plutôt les opérations de stack, car la récursion elle-même est essentiellement une opération de stack.

Vous voulez l’utiliser quand vous avez une structure en arbre. C’est très utile en lecture de XML.

La récursivité, telle qu’elle s’applique à la programmation, consiste essentiellement à appeler une fonction depuis sa propre définition (à l’intérieur de celle-ci), avec des parameters différents pour accomplir une tâche.

“Si j’ai un marteau, fais en sorte que tout ressemble à un clou.”

La récursivité est une stratégie de résolution de problèmes énormes , où, à chaque étape, «transformez deux petites choses en une chose plus grande», chaque fois avec le même marteau.

Exemple

Supposons que votre bureau soit recouvert d’un désordre désorganisé de 1024 papiers. Comment faites-vous une stack de papiers nette et propre à partir du désordre, en utilisant la récursivité?

  1. Diviser: Étalez toutes les feuilles, vous n’avez donc qu’une feuille par “stack”.
  2. Conquérir:
    1. Faites le tour en mettant chaque feuille sur une autre feuille. Vous avez maintenant des stacks de 2.
    2. Faites le tour en mettant chaque stack sur un autre 2 stacks. Vous avez maintenant des stacks de 4.
    3. Contournez chaque stack de 4 stacks. Vous avez maintenant des stacks de 8.
    4. … encore et encore …
    5. Vous avez maintenant une énorme stack de 1024 feuilles!

Notez que c’est assez intuitif, en dehors de tout compter (ce qui n’est pas ssortingctement nécessaire). Vous pourriez ne pas aller jusqu’au bout des stacks de 1 feuille, en réalité, mais vous pourriez et cela fonctionnerait toujours. La partie importante est le marteau: avec vos arm, vous pouvez toujours placer une stack sur l’autre pour créer une stack plus importante, et peu importe la taille de la stack.

La récursivité est le processus par lequel une méthode s’appelle pour pouvoir exécuter 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 rompre l’appel récurrent, c’est-à-dire l’empêcher de s’appeler si une condition est remplie – ceci 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.

Hé, désolé si mon opinion est d’accord avec quelqu’un, j’essaye juste d’expliquer la récursivité en anglais clair.

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

VOICI la récursivité. vous commencez par le haut de la hiérarchie. le coût estival est de 0 $. vous commencez avec Jack, puis vérifiez s’il a des managers en tant qu’employés. Si vous en trouvez, vérifiez s’ils ont des frameworks en tant qu’employés, etc. Ajoutez 300 $ au coût estival chaque fois que vous trouvez un gestionnaire. quand vous en avez fini avec Jack, allez voir John, ses employés et ensuite Morgan.

Vous ne saurez jamais, combien de cycles irez-vous 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 twigs et des feuilles, appelés respectivement parents et enfants. Lorsque vous utilisez un algorithme de récurrence, vous créez plus ou moins consciemment un arbre à partir des données.

En anglais, la récursion signifie répéter plusieurs fois.

Dans la programmation, un exemple consiste à 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) } 

Tout algorithme présente une récursivité structurelle sur un type de données s’il consiste essentiellement en une instruction switch avec une casse 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 récursif structurel 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 le moyen le plus évident d’écrire un algorithme qui fonctionne sur une structure de données.

maintenant, quand on regarde les entiers (enfin, les nombres naturels) tels que définis à l’aide des axiomes de Peano

  integer = 0 | succ(integer) 

vous voyez qu’un algorithme récursif structurel 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 l’exemple le plus sortingvial de cette forme.

function call itself or use its own definition.