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

  Юрий  | 

  |

  Обновл. 22 Ноя 2022  | 

 110688

 ǀ   32 

На этом уроке мы рассмотрим, что такое рекурсия в языке C++ и зачем её использовать, а также последовательность Фибоначчи и факториал целого числа.

Рекурсия

Рекурсивная функция (или просто «рекурсия») в языке 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

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

Рекурсия vs. Итерации

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

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

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

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

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

   глубина рекурсии может быть ограничена;

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

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

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

Правило: Рекомендуется использовать итерацию, вместо рекурсии, но в тех случаях, когда это действительно практичнее. 

Тест


Задание №1

Факториал целого числа 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

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

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

Ответ №3

Задание №4

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

Enter an integer: -14
11111111111111111111111111110010

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

Ответ №4

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

Звёзд: 1Звёзд: 2Звёзд: 3Звёзд: 4Звёзд: 5 (227 оценок, среднее: 4,88 из 5)
Загрузка...

Комментариев: 32

  1. Макс:

    Вот так сделал числа фибоначчи с помощью вектора и цикла

  2. Дмитрий:

    В тестовом задании 4 в ответе мы переводим отрицательное число в положительное и конвертируем уже положительное число в двоичную систему счисления.

    А где же перевод бит в противоположные и прибавление единицы( как говорится в уроке 44)?

    1. Эльдар:

      Всё что свыше значения положительного максимального возможного значения в signed int и есть ряд отрицательных чисел в бинарном представлении с 16-ой единицей вначале.

  3. void:

    моя версия вычисления n-го числа Фибоначчи

  4. Юрий:

    1. Гриша:

      я сразу о векторе подумал)) с вектором проще в коде будет))

  5. Юрий:

    задание №4:

  6. Андрей:

    мой вариант задания №4

  7. Am0k:

    Решил 3 задачу немного по другому, возможно более грубо, но хотелось иметь результат, который можно сразу вывести целиком.

    1. HanGetsu:

      Думал написать подобное, но размер int не позволит преобразовать число больше 1023, если использовать long long, то ограничение уходит до 1048575. Чтоб увеличить размер дальше, как я понял, можно заморочиться играми с памятью на прямую.

  8. Слава:

    Фибоначчи на цикле, без рекурсии.

  9. Alex:

    Более года не видел С++, забросил, писал код на Python.
    Вот пришло время вернуться, повторяю/улучшаю знания по языку.
    Был разговор за Фибоначчи. Рекурсивные функции.

    Решил понять как работает, понял.
    Отняло мин 20 на все, первый раз затупил, чуток не так было, но считало верно.
    Кому интересно смотрите.

    Спасибо за внимание.

    1. Alex:

      В дополнение

      Тут немного подправил вывод Фибоначчи и добавил алгоритм для факториала.

      Код на самом деле проще не бывает, реализация простая, но работает, если кто-то хочет порекомендовать улучшение — приветствуется.

      Да, вот сам код)

  10. Томас:

    В общем, делюсь болью)
    Не понял сначала из условия к третьему заданию что нужно выводить ответ в консоль, а не возвращать значение в коллер.
    Ломал полчаса голову, писал по разному, не получалось, в итоге подсмотрел что вроде и не надо и пошёл дальше.
    А теперь как лёг спать, решение начало крутиться в голове и не давать спать, как обычно, чем больше заставляешь себя думать — тем хуже получается 😀

  11. Виталий:

    Задание №2

  12. Виталий:

    Задание №3 мучелся 3 часа исписал 4 листа А4

  13. Yaroslav:

    Числа Фибоначчи итерация.

  14. cybersatori:

    Да уж, просто пару часов собирал функцию которая у вас в одну строчку во втором задании, зато подружился с отладчиком Visual Studio)

  15. Дима:

    Вопрос, почему когда вызываешь функцию, то числа Фибоначчи после 8 символов идут в периоде, а когда рекурсию то целыми числами.

  16. Yeti:

    4 задание.
    Вроде все выполняется как надо ¯\_(ツ)_/¯

    1. Nikita:

      Ну отлично. Единственное что в идеале ещё добавить, так это случай когда вместо числа, введут символ.

    2. Viktor:

      То же самое сделал)) Вообще не очень понимаю пока что как в дальнейшем использовать рекурсию.

  17. ZiF1R:

    Немного доработал код из 1 задания.

    /*Output:
    1! = 1
    2! = 2
    3! = 6
    4! = 24
    5! = 120
    6! = 720
    7! = 5040
    */

    1. SuRprizZe:

      Сделал номер 4 вот так, все работает вывод такой же…

      1. Андрей:

        В Вашем случае при вводе пользователем 0 вывода не будет.

  18. Александр:

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

    Я бы на примере этой функции советовал очень аккуратно относиться к рекурсивным функциям, которые вызывают более одного своего экземпляра (эта проблема легко лечится, но само ее возникновение не так очевидно для начинающих)

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

    Очень простой пример: вывод последовательности в обратном порядке (последовательность читаем до 0).
    рекурсивное решение:

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

    ЗЫ Спорить о том, как лучше нет смысла. Пример приведен исключительно, чтобы показать, что "тупо в лоб" рекурсия на цикл не заменяется. Можно рассмотреть более сложные примеры из комбинаторики, для которых рекурсия простая и очевидная, а реализация решения итеративно просто выносит мозг.

    1. Fakovka999:

      Соглашусь с вами, делал свою функцию — альтернативу "itos" (int в string)

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

    2. Инкогнито:

      Ану переведи мне постоянный цикл, использующийся для обновления частоты экрана в рекурсию…

  19. Александр:

    @@@
    Поскольку функция countOut() никогда ничего не возвращает (она просто снова вызывает countOut()), то данные этой функции никогда не вытягиваются из стека!
    @@@

    Нет… данные не извлекаются из стека не потому, что функция ничего не возвращает… можно переписать ее код так:

    и она все еще ничего не будет возвращать (да и как она что-то может вернуть, если она void? )

    корректней сказать, что ни одна из функций не завершается, так как она ожидает завершения вызванной ей копии. Ну или как-то в этом роде…

    Оно то понятно, что имеется в виду под "не возвращает", но для этого "понятно" нужно уже что-то знать, а тексты вроде как для новичков позиционируются 🙂

    1. Andrew Gulenko:

      Спасибо. Так точно понятние.

    2. Антон:

      ну не знаю, если человек дошел до сюда, и хорошо понимает что void не возвращает ничего, то, как по мне, можно догадаться, что имелось в виду автором, да и те кто читают уроки про рекурсию, уже явно не те новички, которыми были перед тем как прочитали эти 100 уроков

  20. kmish:

    2е задание:

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

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