Recursion C ++





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

En C ++ toute fonction sauf principale() Il peut appeler lui-même. То есть в теле функции может быть размещен вызов этой же функции. Это называется рекурсией.

Когда программа выполняет код рекурсивной функцииона будет выполнять его бесконечно, если не предусмотреть условие выхода из рекурсии. Об этом надо помнить, чтобы избежать зацикливания вызовов. Поэтому в определении рекурсивной функции обязательно надо указывать условие выхода. par exemple, можно разместить её вызов внутри блока si.

В этой программе функция recursionGoDown() будет вызывать саму себя, пока в нее передается число больше нуля. à chaque fois que, функция получает число, от которого в сигнатуре отнимается единица. Как только условие станет ложным (число станет меньше нуля) – вызовы остановятся и начнется выход из рекурсии.

Если мы передаем в такую функцию число 9, вызовов будет 10. Программа как бы углубляется на 10 уровней, выполняя рекурсию. Чтобы ей выйти из рекурсии, надо пройти эти десять уровней обратно. Так строка кода

будет выполняться тоже 10 temps, но значение someNumber будет меняться в обратном порядке. Сначала оно будет соответствовать тому, что передалось в функцию на 10 уровне рекурсии, потом тому что передалось на 9 уровне и т.д.

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

Хочу обратить внимание на важный момент. При каждом рекурсивном вызове создается новая переменная someNumber с новым значением. Эти переменные будут занимать какое-то место в оперативной памяти. Если вызовов 10, dans cet exemple,, то и в памяти будет храниться 10 переменных с разными значениями. Можно дописать в программу вывод на экран адресов, по которым хранятся эти значения и убедиться в этом:

Передаем в функцию число 2: recursionGoDown(2); Уровней рекурсии будет 3.

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

Comme on le voit, каждое значение переменной someNumber хранится в отдельном отрезке памяти. Во время обратного выхода по рекурсии значения берутся из тех же адресов но в обратном порядке.

Практически каждую поставленную задачу, которую можно решить используя рекурсию, можно реализовать используя итерации циклов. Вы ведь легко можете показать на экран числа от 9 à 0 и от 0 à 9 применив циклы. Помимо этого следует знать, что рекурсия займет больше памяти и будет производить вычисления медленнее, чем итерация.

mais, как утверждают опытные программисты и многие авторы книг, это не значит, 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. Для начального уровня, 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:

date
page
Recursion C ++
évaluation
51star1star1star1star1star

4 réflexions sur "Recursion C ++

  1. Вы слишком строги к рекурсии ;-)

    1. Recursion – это общий математический аппарат, которым теоретически выражаются все вычислимые алгоритмы (это я взял из мат. теории алгоритмов).
    2. Все задачи над динамическими структурами данных (списки, очереди, деревья, графы, …) решаются рекурсивно проще, а главное нагляднее, чем итерационно (итерационные циклические алгоритмы лучше работают над массивамистатическими конструкциями).
    3. Есть алгоритмы, которые выражаются в 2-3 строчки рекурсивно, но которые крайне сложно выписать без рекурсии. Красивейший пример тому: знаменитая задача “Tour de Hanoi”. Многие алгоритмы сортировки (тех же массивов) лучше выражаются в рекурсивной форме.

    Рекурсия только кажется сложной, потому что ей не учат в отечественной практике и не умеют её применять. А в университетах Франции, par exemple, обучение 1-го семестра начинают с обучения рекурсивным алгоритмам.

    1. Всегда хорошо, когда кто-то высказывает свою точку зрения и свое личное мнение, основанное на опыте. Начинающим полезно будет почитать.

    2. Как вы предлагаете использовать рекурсию в списках и очередях?

      1. Recursion – il самый естественный способ обработки любых динамических структур (списков, деревьев и т.д.), это демонстрируют функциональные языки программирования, такие как Lisp. Такой подход намного эффективней, чем итерационный (циклами). Но это нужно показывать на примерах кода
        А простой и красивый пример рекурсии посмотрите в задаче возведения числа в степень: http://purecodecpp.com/archives/2734

Laisser un commentaire

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