Recursion C ++

Recursion C ++
5 (100%) 1 vote





рекурсия с++, Fibonacci c ++

En C ++ toute fonction sauf principale() Il peut appeler lui-même. Cela est, dans le corps de la fonction peut être placé un appel à cette même fonction. Ceci est appelé récursion.

Lorsque le programme exécute le code d'une fonction récursive – il réalisera son infini, si vous ne fournissez pas une condition de sortie de la récursion. Cela devrait se rappeler, pour éviter les appels en boucle. Par conséquent, pour déterminer la fonction récursive doit certainement indiquer la condition de sortie. par exemple, vous pouvez le placer dans l'appel de bloc si.

Dans ce programme, la fonction recursionGoDown() va appeler lui-même, jusqu'à ce qu'il soit transféré à un nombre supérieur à zéro. à chaque fois que, fonction obtient le nombre de, à partir de laquelle est soustraite de l'unité de signature. Dès que la condition devient fausse (le nombre sera inférieur à zéro) – les appels à arrêter et démarrer la sortie de la récursion.

Si nous passons dans un numéro de fonction 9, appels 10. Le programme tel qu'il approfondit sur 10 niveaux, récursion exécution. Pour la sortir de la récursion, Nous devons passer ces dix niveaux de retour. Depuis la ligne de code

Il sera effectué aussi 10 temps, mais la valeur someNumber va changer dans l'ordre inverse. Tout d'abord, il correspondra au, qui a été transmis à la fonction dans la 10 niveau de récursivité, puis transmis au fait que 9 niveau, etc..

рекурсия с++, Fibonacci c ++

Je veux attirer l'attention sur un point important. A chaque appel récursif crée une nouvelle variable someNumber avec la nouvelle valeur. Ces variables occuperont une place dans la mémoire. Si l'appel 10, dans cet exemple,, et il sera stocké dans la mémoire 10 variables avec des valeurs différentes. Nous pouvons ajouter à la sortie du programme aux adresses écran, qui stocke ces valeurs et voir ce:

Nous sommes passés au numéro de fonction 2: recursionGoDown(2); Les niveaux de récursivité est 3.

рекурсия с++, Fibonacci c ++

Comme on le voit, chaque valeur de la variable someNumber stocké dans un segment de mémoire distinct. Au cours de la sortie inverse des valeurs de récursion sont prises au même endroit, mais dans l'ordre inverse.

Presque toutes les tâches, qui peut être résolu en utilisant récursion, peut être mis en œuvre à l'aide cycles d'itération. Parce que vous pouvez facilement montrer aux numéros d'écran de 9 à 0 et 0 à 9 appliquer cycles. En plus de cela, vous devez savoir, que la récursion prendra plus de mémoire et de calcul produira plus lentement, itération cem.

mais, Selon les programmeurs expérimentés et de nombreux auteurs de livres, cela ne signifie pas, que la récursivité est inutile. Il y a des tâches, décider, Utilisation de cycles d'itération, difficile et encombrant. Une solution récursive semble mieux. Pour niveau d'entrée, jusqu'à ce que vous apprenez seulement bases de la programmation en C ++, vous avez juste besoin de comprendre, quel récursivité est et comment il fonctionne.

Voir plus de vidéos sur les Recursion 6′ (Auteur vidéo: Denis Markov).

Bulletin de nouvelles leçons sur la programmation:

4 réflexions sur "Recursion C ++

  1. Vous êtes trop dur récursion ;-)

    1. Recursion – un formalisme mathématique général, qui expriment théoriquement tous les algorithmes calculables (Je l'ai sorti du tapis. théorie des algorithmes).
    2. Toutes les tâches de structures de données dynamiques (listes, file, arbres, compte, …) résolu de manière récursive plus facile, et surtout plus claire, que itérativement (travail cycliques algorithmes itératifs mieux sur les tableaux – structures statiques).
    3. il y a des algorithmes, qui sont exprimés en 2-3 ligne récursive, mais qui est extrêmement difficile à écrire sans récursion. Un bel exemple de cette: célèbre problème “Tour de Hanoi”. De nombreux algorithmes de tri (la même baie) mieux exprimée sous la forme de récursif.

    Récursion semble juste compliqué, parce qu'il est pas enseignée dans la pratique nationale et ne savent pas comment l'utiliser. Et dans les universités en France, par exemple, la formation du 1er semestre commence avec l'apprentissage des algorithmes récursifs.

      1. Recursion – il le plus naturel un procédé de traitement des structures dynamiques (listes, arbres, etc.), cela est démontré par les langages de programmation fonctionnelle, tels que Lisp. Une telle approche est beaucoup plus efficace, que itérative (cycles). Mais il faut montrer des exemples de code…
        Un exemple simple et belle de récursion se pencher sur le problème d'un nombre élevé à une puissance: http://purecodecpp.com/archives/2734

Laisser un commentaire

Placez le code dans les balises: <pre class="lang:c ++ décodage:true ">VOTRE CODE</pré>