Урок 107. Рекурсия. Числа Фибоначчи и Факториал

   ⁄ 

 Обновлено 15 Янв 2018  ⁄ 

⁄   2738

Рекурсивная функция (рекурсия) в C++ — это функция, которая вызывает саму себя. Например:

При вызове countOut(4) на экран выведется «push 4», а затем вызовется countOut(3). countOut(3) выведет «push 3» и вызовет countOut(2). Последовательность вызова countOut(n) других функций countOut(n-1) повторяется бесконечное количество раз (аналог бесконечного цикла). Попробуйте запустить у себя.

В уроке о Стеке и Куче мы узнали, что при каждом вызове функции, определенные данные помещаться в стек вызовов. Поскольку функция countOut() никогда ничего не возвращает (она просто снова вызывает countOut()), то данные этой функции никогда не вытягиваются из стека! Следовательно, в какой-то момент память стека закончится и результатом будет переполнение стека – в программе произойдет сбой, и она завершится.

Условие завершения рекурсии

Рекурсивные вызовы функций работают так же, как и обычные вызовы функций. Однако программа выше иллюстрирует наиболее важное отличие простых функций от рекурсивных: вы должны указывать условие завершения рекурсии, или функция будет выполняться «бесконечно» (фактически, до тех пор, пока не исчерпается память в стеке вызовов). Условие завершения рекурсии — это условие, которое, при его выполнении, остановит вызов рекурсивной функции саму себя.

В этом условии обычно используется оператор if. Вот пример функции выше, но уже с условием завершения рекурсии (и еще с одним дополнительным выводом текста):

Когда мы запустим эту программу, countOut() начнет выводить:

push 4
push 3
push 2
push 1

Если сейчас посмотреть на стек вызовов, то увидим следующее:



countOut(1)
countOut(2)
countOut(3)
countOut(4)
main()

Из-за условия завершения countOut(1) не вызовет countOut(0) — условие if не выполнится и поэтому выведется «pop 1» и countOut(1) завершит своё выполнение. На этом этапе countOut(1) вытягивается из стека, и управление возвращается к countOut(2). countOut(2) возобновляет выполнение в точке после вызова countOut(1), поэтому выведется «pop 2», а затем countOut(2) завершится. Рекурсивные вызовы функций countOut постепенно вытягиваются из стека до тех пор, пока не будут удалены все экземпляры countOut.

Таким образом, полный результат выполнения программы выше:

push 4
push 3
push 2
push 1
pop 1
pop 2
pop 3
pop 4

Стоит отметить, что «push» выводится в порядке убывания, а «pop» в порядке возрастания. Дело в том, что «push» выводится до вызова рекурсивной функции, а «pop» выполняется (выводится) после вызова рекурсивной функции, когда все экземпляры countOut вытягиваются из стека (что происходит в обратном порядке, в котором эти экземпляры были введены).

Еще рекурсия

Теперь, когда мы обсудили основной механизм вызова рекурсивных функций, давайте взглянем на несколько другой тип рекурсии, который более распространен:

Рассмотреть рекурсию с первого взгляда на код не так уж и легко. Лучшим вариантом будет посмотреть, что произойдет при вызове рекурсивной функции с определенным значением. Например, посмотрим, что произойдет при вызове функции выше с value = 4.

sumCount(4). 4 > 1, поэтому возвращается sumCount(3) + 4.
sumCount(3). 3 > 1, поэтому возвращается sumCount(2) + 3.
sumCount(2). 2 > 1, поэтому возвращается sumCount(1) + 2.
sumCount(1). 1 = 1, поэтому возвращается 1. Это условие завершения рекурсии.

Теперь посмотрим на стек вызовов:

sumCount(1) возвращает 1.
sumCount(2) возвращает sumCount(1) + 2, т.е. 1 + 2 = 3.
sumCount(3) возвращает sumCount(2) + 3, т.е. 3 + 3 = 6.
sumCount(4) возвращает sumCount(3) + 4, т.е. 6 + 4 = 10.

На этом этапе уже легче увидеть, что мы просто добавляем числа между 1 и значением, которое предоставил caller. На практике рекомендуется указывать комментарии возле рекурсивных функций, дабы облегчить жизнь не только себе, но, возможно, и другим людям, которые будут просматривать ваш код.

Рекурсивные алгоритмы

Рекурсивные функции обычно решают проблему, сначала найдя решение для подмножеств проблемы (рекурсивно), а затем модифицируя это «подрешение», дабы добраться уже до верного решения. В примере выше алгоритм sumCount(value) сначала решает sumCount(value-1), а затем добавляет значение value, чтобы найти решение для sumCount(value).

Во многих рекурсивных алгоритмах некоторые данные ввода производят предсказуемые данные вывода. Например, sumCount(1) имеет предсказуемый вывод 1 (вы можете легко это вычислить и проверить самостоятельно). Случай, когда алгоритм при определенных данных ввода производит предсказуемые данные вывода — называется базовым случаем. Базовые случаи работают как условия завершения алгоритма. Их часто можно идентифицировать, рассматривая результаты вывода для следующих значений ввода: 0, 1, «» или null.

Числа Фибоначчи

Одним из наиболее известных математических рекурсивных алгоритмов является последовательность Фибоначчи. Последовательности Фибоначчи можно рассмотреть во многих местах природы, таких как ветвление деревьев, спираль раковин, плоды ананаса, разворачивающийся папоротник и т.д.

Спираль Фибоначчи выглядит следующим образом:

Каждое из чисел Фибоначчи — это длина горизонтальной стороны квадрата, в которой находится данное число. Математически числа Фибоначчи определяются как:

F(n) = 0 если n = 0
1 если n = 1
f(n-1) + f(n-2) если n > 1

Следовательно, довольно просто написать рекурсивную функцию для вычисления n-го числа Фибоначчи:

Результат выполнения программы выше:

0 1 1 2 3 5 8 13 21 34 55 89 144

Заметили? Это те же числа, что и в спирали Фибоначчи.



Рекурсия против Итерации

Наиболее популярный вопрос, который задают о рекурсивных функциях — «Зачем использовать рекурсивную функцию, если задание можно выполнить с помощью итераций (используя цикл for или цикл while)?». Оказывается, вы всегда можете решить рекурсивную проблему итеративно — однако для нетривиальных задач рекурсивная версия часто бывает намного проще — как для написания, так и для чтения. Например, функцию вычисления n-го числа Фибоначчи можно написать и методом итераций, но это будет немного сложнее! (Попробуйте!)

Итеративные функции (те, которые используют циклы for или while) почти всегда более эффективны, чем их рекурсивные аналоги. Это связано с тем, что каждый раз, при вызове функции, расходуется определенное количество ресурсов, которое тратится на добавление и вытягивание фреймов из стека. Итеративные функции расходуют намного меньше этих ресурсов.

Это не значит, что итеративные функции всегда являются лучшим выбором. Иногда рекурсивная реализация может быть чище и проще и некоторые дополнительные расходы могут быть более чем оправданы, сведя к минимуму трудности при будущей поддержке кода, особенно если алгоритм не требует слишком много времени для поиска решения.

В общем, рекурсия является хорошим выбором, если выполняется большинство из следующих утверждений:

  Рекурсивный код намного проще реализовать.

  Глубина рекурсии может быть ограничена (т.е. когда caller точно не предоставит число, при котором рекурсия будет выполняться 100 000 раз).

  Итеративная версия алгоритма требует управления стеком данных.

  Это не критическая часть кода, которая напрямую влияет на производительность программы.

Совет: Если рекурсивный алгоритм проще реализовать, то имеет смысл начать с рекурсии, а затем, позже, оптимизировать код в итеративный алгоритм.

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

Тест

Задание №1

Факториал целого числа N (записанный как N!) определяется как произведение (умножение) всех чисел между 1 и N (0! = 1). Напишите рекурсивную функцию factorial, которая возвращает факториал ввода. Протестируйте её с помощью первых 8 чисел.

Подсказка: Помните, что x * y = y * x, поэтому произведение всех чисел между 1 и N – это тоже самое, что и произведение всех чисел между N и 1.

Ответ 1

Задание №2

Напишите рекурсивную функцию, которая принимает целое число в качестве ввода и возвращает сумму всех чисел этого значения (например, 482 = 4 + 8 + 2 = 14). Протестируйте вашу программу числом 83569 (результатом должно быть 31).

Ответ 2

Задание №3

Это уже немного сложнее. Напишите программу, которая просит пользователя ввести целое число, а затем использует рекурсивную функцию для вывода бинарного представления этого числа. Смотрите урок о переводе чисел из бинарной системы в десятичную и наоборот. Предполагается, что число, которое введет пользователь — положительное.

Подсказка: Используя способ №1 для конвертации чисел из десятичной системы в двоичную из урока, вам нужно будет выводить биты «снизу вверх», т.е. в обратном порядке. Для этого, ваш строчка вывода должна находиться после вызова рекурсии.

Ответ 3

Задание №4

Используя программу из задания №3, обработайте случай, когда пользователь введет 0 или отрицательное число.

Например:

Enter an integer: -14
11111111111111111111111111110010

Подсказка: Вы можете превратить отрицательное целое число в положительное, используя static_cast для конвертации в unsigned int.

Ответ 4

Оценить статью:

Звёзд: 1Звёзд: 2Звёзд: 3Звёзд: 4Звёзд: 5 (20 оценок, среднее: 5,00 из 5)
Загрузка...
Подписаться на обновления:

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *

ПОДПИСЫВАЙТЕСЬ

НА КАНАЛ RAVESLI В TELEGRAM

@ravesli

ПОДПИСАТЬСЯ БЕСПЛАТНО