Рекурсия в С++

Оцени эту статью





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

В C++ любая функция кроме main() может вызывать саму себя. То есть в теле функции может быть размещен вызов этой же функции. Это называется рекурсией.

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

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

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

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

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

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

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

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

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

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

Но, как утверждают опытные программисты и многие авторы книг, это не значит, что рекурсия бесполезна. Есть задачи, решать которые, используя итерации циклов, сложно и громоздко. А рекурсивное решение выглядит лучше. Для начального уровня, пока вы изучаете только основы программирования на C++, вам достаточно просто понимать, что из себя представляет рекурсия и как она работает.

Посмотрите ещё видео по теме Рекурсия с 6′ (Автор видео: Денис Марков).

Рассылка новых уроков по программированию:

Рекурсия в С++: 4 комментария

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

    1. Рекурсия — это общий математический аппарат, которым теоретически выражаются все вычислимые алгоритмы (это я взял из мат. теории алгоритмов).
    2. Все задачи над динамическими структурами данных (списки, очереди, деревья, графы, …) решаются рекурсивно проще, а главное нагляднее, чем итерационно (итерационные циклические алгоритмы лучше работают над массивами — статическими конструкциями).
    3. Есть алгоритмы, которые выражаются в 2-3 строчки рекурсивно, но которые крайне сложно выписать без рекурсии. Красивейший пример тому: знаменитая задача «Ханойская башня». Многие алгоритмы сортировки (тех же массивов) лучше выражаются в рекурсивной форме.

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

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

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

Добавить комментарий

Код размещайте в тегах: <pre class="lang:c++ decode:true ">YOUR CODE</pre>