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

Question

L'un des sujets qui semble revenir régulièrement sur les listes de diffusion et les discussions en ligne est les mérites (ou l'absence de mérite) d'obtenir 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écursion ?
2. Quand devrais-je utiliser la récursivité ?
3. Pourquoi les gens n'utilisent-ils pas la récursivité ?

Answer 1

Il existe un certain nombre de bonnes explications ré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 langages impératifs (c'est-à-direchaque implémentation majeure de C, C++, Basic, Python, Ruby, Java et C#) itération est largement préférable à la récursivité.

Pour comprendre pourquoi, parcourez les étapes utilisées par les langages ci-dessus pour appeler une fonction :

1. l'espace est découpé sur la pile pour les arguments et les variables locales de la fonction
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 que ce qu'il faut pour parcourir une boucle.Cependant, le vrai problème réside dans l’étape n°1.Lorsque de nombreux programmes démarrent, ils allouent un seul morceau de mémoire pour leur pile, et lorsqu'ils manquent de mémoire (souvent, mais pas toujours à cause de la récursivité), le programme plante en raison d'un problème. débordement de pile.

Ainsi, dans ces langages, la récursion est plus lente et vous rend vulnérable aux plantages.Il existe néanmoins quelques arguments en faveur de son utilisation.En général, le code écrit de manière récursive est plus court et un peu plus élégant, une fois que vous savez le lire.

Il existe une technique que les implémenteurs de langage peuvent utiliser, appelée optimisation des appels de queue ce qui peut éliminer certaines classes de débordement de pile.En termes succincts :si l'expression de retour d'une fonction est simplement le résultat d'un appel de fonction, alors vous n'avez pas besoin d'ajouter un nouveau niveau sur la pile, vous pouvez réutiliser celui actuel pour la fonction appelée.Malheureusement, peu d’implémentations de langages impératifs intègrent une optimisation des appels finals.

* 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 à plusieurs reprises.Je ne pense tout simplement pas que la récursivité soit généralement une bonne idée dans les langages qui ne sont pas adaptés à cela.

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

Answer 2

Exemple anglais simple de récursion.

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.

Answer 3

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

struct Node {
    Node* next;
};

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

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

(Cela pourrait bien sûr également être fait avec une boucle for, mais c'est utile pour illustrer le concept)

Answer 4

Chaque fois qu'une fonction s'appelle elle-même, créant une boucle, il s'agit alors d'une récursion.Comme pour toute chose, il y a de bonnes et de mauvaises utilisations de la récursivité.

L'exemple le plus simple est la récursion 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, 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 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écursivité plutôt que de l'itération devrait être de tirer parti de la pile d'appels 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 une façon d'accomplir ramification.Un exemple classique est le Triangle de Sierpinski.

Vous pouvez en dessiner un très simplement avec récursion, où la pile d'appels se divise 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.

D'autres cas d'utilisation courants peuvent inclure la traversée de hiérarchies, par ex.robots d'exploration de sites Web, comparaisons d'annuaires, etc.

Conclusion

En termes pratiques, la récursivité est la plus logique chaque fois que vous avez besoin d'un branchement itératif.

Answer 5

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

L'exemple canonique est une routine pour générer la Factorielle de n.La factorielle de n est calculée en multipliant tous les nombres compris 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 dans la solution itérative et elle devrait avoir du sens pour toute personne familiarisée avec C#.

La solution récursive est trouvée en reconnaissant que la nième factorielle est n * Fact(n-1).Ou, pour le dire autrement, si vous savez ce qu'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 de Cas 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.

Lorsqu'on le rencontre pour la première fois, cela peut être un peu déroutant, il est donc instructif d'examiner son fonctionnement lors de son exécution.Imaginez que nous appelions FactRec(5).Nous entrons dans la routine, ne sommes pas repris 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 rentrons dans la méthode avec le paramètre 4, nous ne sommes à nouveau pas arrêtés par la clause guard et nous nous retrouvons donc à :

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

Si nous remplaçons cette valeur de retour par 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 montrer chaque étape du processus :

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 scénario 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 à la méthode entraîne soit le déclenchement d'un cas de base, soit un appel à la même méthode dont 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.

Answer 6

La récursivité consiste à résoudre 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 ce problème en C# pour les entiers positifs (non testé - il peut y avoir un bug).

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

    return n * Factorial(n - 1);
}

Answer 7

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 ainsi que d'autres calculs pour formuler la réponse au problème d'origine.Souvent, dans le processus de résolution de la version 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 trivial à résoudre.

Par exemple, pour calculer une factorielle pour le nombre X, on peut le représenter comme X times the factorial of X-1.Ainsi, la méthode « récursive » pour trouver la factorielle de X-1, puis multiplie tout ce qu'il a obtenu X pour donner une réponse définitive.Bien sûr, pour trouver la factorielle de X-1, il va 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 retourner 1 depuis 0! = 1! = 1.

Answer 8

Considérez un problème ancien et bien connu:

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

La définition de pgcd est étonnamment simple :

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

En anglais, cette définition dit que le plus grand diviseur commun de tout nombre et zéro est ce nombre, et le plus grand diviseur commun de deux nombres. m et n est le plus grand diviseur commun de n et le reste après division m par n.

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

Calculons pgcd(10, 8) à titre d'exemple.Chaque étape est égale à celle qui la précède :

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 deuxième partie s'applique à nouveau, mais cette fois 8 mod 2 = 0 car 2 divise 8 sans reste.A l'étape 5, le deuxième argument est 0, donc la réponse est 2.

Avez-vous remarqué que pgcd apparaît à gauche et à droite du signe égal ?Un mathématicien dirait que cette définition est récursive parce que l'expression que vous définissez se reproduit à l'intérieur de sa définition.

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

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

où head est le premier élément d'une liste et tail est le reste de la liste.Noter que sum revient dans sa définition à la fin.

Peut-être préféreriez-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 la transformer en une série d'additions :

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

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

Tri par fusion 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 omniprésentes si vous savez quoi 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 en arriver aux réponses faciles.

Avec cette compréhension, vous pouvez désormais apprécier les autres algorithmes de Article de Wikipédia sur la récursivité!

Answer 9

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 plus petite partie 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 (la surcharge des appels de fonction a tendance à être élevée car les fonctions récursives ont tendance à être petites, voir ci-dessus) et peut souffrir de certains problèmes (débordement de pile, quelqu'un ?).Certains disent qu'ils ont tendance à être difficiles à obtenir « correctement » dans des cas non triviaux, mais je n'y crois pas vraiment.Dans certaines situations, la récursion est la plus logique et constitue la manière la plus élégante et la plus claire d’écrire une fonction particulière.Il est à noter que certains langages privilégient les solutions récursives et les optimisent beaucoup plus (on pense à LISP).

Answer 10

Une fonction récursive est une fonction qui s'appelle elle-même.La raison la plus courante pour laquelle je l'utilise est la traversée d'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 souhaiterais peut-être 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 transmis, puis s'appelle 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 vois pas de 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é une mauvaise réputation dans certains cercles.

Answer 11

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

Considérons les acronymes récursifs comme exemple simple :

• GNOU représente GNU n'est pas Unix
• PHP représente PHP :Hypertext Preprocessor
• YAML représente YAML n'est pas un langage de balisage
• VIN représente Le vin n'est pas un émulateur
• VISA représente Association des services internationaux de visa

Plus d'exemples sur Wikipédia

Answer 12

La récursivité fonctionne mieux avec ce que j'aime appeler des « problèmes fractaux », où vous avez affaire à une grande chose composée 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 parcourir 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écursion.

Les gens évitent la récursion pour un certain nombre de raisons :

1. La plupart des gens (moi y compris) ont fait leurs armes en programmation avec 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 ont fait leurs armes en programmation procédurale ou orientée objet ont souvent été invités à éviter la récursion car elle est sujette aux erreurs.

3. On nous dit souvent que la récursivité est lente.L'appel et le retour répétés d'une routine impliquent beaucoup de poussées et de sauts de pile, ce qui est plus lent que la boucle.Je pense que certains langages gèrent cela mieux 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, car sa pile n'est pas si profonde.

Answer 13

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, prenons factorielle :

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, le problème de 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 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 à ce que vous avez "déjà fait" via la même procédure.(c'est à dire. factorial(n) = n*factorial(n-1))

2) Une partie de base, qui garantit que le processus ne se répète pas indéfiniment en lui donnant un point de départ (c'est-à-dire factorial(1) = 1)

Cela peut être un peu déroutant de s'y retrouver au début, mais il suffit de regarder quelques exemples et tout devrait s'assembler.Si vous souhaitez une compréhension beaucoup plus approfondie du concept, étudiez l’induction mathématique.Sachez également que certains langages optimisent les appels récursifs alors 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...

Answer 14

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 morceaux plus petits, puis s’appelle pour résoudre chacun des morceaux plus petits.

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

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

Un problème avec manuels d'informatique est que ils présentent des exemples stupides de récursion.Les exemples typiques sont les suivants: calcul d'une factorielle ou calcul d'une La séquence de Fibonacci.La récursion est une outil puissant, et il est vraiment stupide à utiliser dans l'un ou l'autre de ces cas.Si une programmeur qui a travaillé pour moi utilisé récursion pour calculer une factorielle, je engager quelqu'un d'autre.

J'ai pensé que c'était un point très intéressant à soulever et que c'était peut-être une des raisons pour lesquelles la récursivité est souvent mal comprise.

MODIFIER:Ce n'était pas une fouille dans la réponse de Dav - je n'avais pas vu cette réponse lorsque j'ai posté ceci

Answer 15

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

Answer 16

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 décompte est de 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 d'articles il y a.

1. l'ensemble est [x x x] 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 [x x] (c'est-à-direnous avons supprimé un élément).
2. l'ensemble est [x x], 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 [x x x], qui est 3.Hourra!

Nous pouvons représenter cela comme suit :

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

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 "utilisé" 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 disposez encore de 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 à l'ensemble de données plus petit".

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

Answer 17

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

Lorsque les gens parlent de « récursivité », ils parlent généralement d'une fonction qu'ils ont écrite et qui s'appelle à plusieurs reprises jusqu'à ce qu'elle ait terminé son travail.La récursivité peut être utile lors du parcours des hiérarchies dans les structures de données.

Answer 18

Un exemple:Une définition récursive d’un escalier est :Un escalier se compose de :- une seule marche et un escalier (récursion) - soit en une seule étape (arrêt)

Answer 19

Pour récurer sur un problème résolu :ne faites rien, c'est fini.
Pour récurer sur un problème ouvert :faites l'étape suivante, puis récurez le reste.

Answer 20

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

1. Prends une pomme
2. Notez les notes 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 en 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 consistant à répéter la même chose jusqu’à ce que vous ayez terminé est appelé récursivité.

J'espère que c'est la réponse « en anglais simple » que vous recherchez !

Answer 21

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érons deux miroirs se faisant face.Nous avons vu l’effet infini qu’ils produisent.Chaque reflet 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écursion.

UN arbre de recherche binaire est un bon exemple de programmation de 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 binaire sont également récursives.

Answer 22

C'est une vieille question, mais je souhaite ajouter une réponse d'un 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écursion, je devrai peut-être définir une fonction externe (qui existe uniquement parce que mon code se heurte à la règle bureaucratique de Java), ou je devrai peut-être refactoriser complètement le code (ce que je déteste vraiment faire).

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

Answer 23

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

Answer 24

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

Answer 25

"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 pour énorme des problèmes, où à chaque étape, il suffit de "transformer 2 petites choses en une plus grande chose", à chaque fois avec le même marteau.

Exemple

Supposons que votre bureau soit recouvert d'un désordre désorganisé de 1 024 papiers.Comment créer une pile de papiers nette et propre à partir du désordre, en utilisant la récursion ?

1. Diviser: Étalez toutes les feuilles pour n'avoir qu'une seule feuille dans chaque "pile".
2. Conquérir:
   2. Faites le tour en plaçant chaque feuille sur une autre feuille.Vous disposez désormais de piles de 2.
   3. Faites le tour en plaçant chaque 2 piles au-dessus d’une autre 2 piles.Vous disposez désormais de piles de 4.
   4. Faites le tour en plaçant chaque pile de 4 au-dessus d’une autre pile de 4.Vous disposez désormais de piles de 8.
   5. ...encore et encore ...
   6. Vous disposez maintenant d’une énorme pile de 1024 feuilles !

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

Answer 26

La récursivité est le processus par lequel une méthode s'appelle elle-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écussif, c'est-à-direl'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 à une utilisation récursive.

Answer 27

hé, désolé si mon opinion 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 300 $ à chaque manager et vous voulez savoir combien cela coûterait.La réponse est évidente : et si deux des employés de Morgan étaient également des managers ?

VOICI vient la récursion.vous partez du haut de la hiérarchie.le coût estival est de 0$.Tu commences avec Jack, Ensuite, vérifiez s'il a des gestionnaires comme employés.si vous trouvez que l'un d'entre eux le fait, vérifiez s'il a des managers comme employés, etc.Ajoutez 300$ au coût estival à chaque fois que vous trouvez un manager.lorsque vous en avez fini avec Jack, allez voir John, ses employés puis chez Morgan.

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

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

Answer 28

En clair, la récursivité signifie répéter quelque chose encore et encore.

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

Answer 29

Tout algorithme présente de construction la récursivité sur un type de données 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 fonctionnant sur une structure de données.

maintenant, quand vous regardez 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 structurel récursif sur des 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 bien connue est à peu près l'exemple le plus trivial de ce formulaire.

Answer 30

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