На этом уроке мы рассмотрим, что такое рекурсия в языке C++ и зачем её использовать, а также последовательность Фибоначчи и факториал целого числа.
Рекурсия
Рекурсивная функция (или просто «рекурсия») в языке C++ — это функция, которая вызывает сама себя. Например:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> void countOut(int count) { std::cout << "push " << count << '\n'; countOut(count-1); // функция countOut() вызывает рекурсивно сама себя } int main() { countOut(4); return 0; } |
При вызове функции countOut(4) на экран выведется push 4
, а затем вызывается countOut(3). countOut(3) выведет push 3
и вызывает countOut(2). Последовательность вызова countOut(n) других функций countOut(n-1) повторяется бесконечное количество раз (аналог бесконечного цикла). Попробуйте запустить у себя.
На уроке о стеке и куче в С++ мы узнали, что при каждом вызове функции, определенные данные помещаются в стек вызовов. Поскольку функция countOut() никогда ничего не возвращает (она просто снова вызывает countOut()), то данные этой функции никогда не вытягиваются из стека! Следовательно, в какой-то момент, память стека закончится и произойдет переполнение стека.
Условие завершения рекурсии
Рекурсивные вызовы функций работают точно так же, как и обычные вызовы функций. Однако, программа, приведенная выше, иллюстрирует наиболее важное отличие простых функций от рекурсивных: вы должны указать условие завершения рекурсии, в противном случае — функция будет выполняться «бесконечно» (фактически до тех пор, пока не закончится память в стеке вызовов).
Условие завершения рекурсии — это условие, которое, при его выполнении, остановит вызов рекурсивной функции самой себя. В этом условии обычно используется оператор if.
Вот пример функции, приведенной выше, но уже с условием завершения рекурсии (и еще с одним дополнительным выводом текста):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> void countOut(int count) { std::cout << "push " << count << '\n'; if (count > 1) // условие завершения countOut(count-1); std::cout << "pop " << count << '\n'; } int main() { countOut(4); return 0; } |
Когда мы запустим эту программу, то 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() вытягиваются из стека (это происходит в порядке, обратном тому, в котором эти экземпляры были введены в стек).
Теперь, когда мы обсудили основной механизм вызова рекурсивных функций, давайте взглянем на несколько другой тип рекурсии, который более распространен:
1 2 3 4 5 6 7 8 9 10 |
// Возвращаем сумму всех чисел между 1 и value int sumCount(int value) { if (value <= 0) return 0; // базовый случай (условие завершения) else if (value == 1) return 1; // базовый случай (условие завершения) else return sumCount(value - 1) + value; // рекурсивный вызов функции } |
Рассмотреть рекурсию с первого взгляда на код не так уж и легко. Лучшим вариантом будет посмотреть, что произойдет при вызове рекурсивной функции с определенным значением. Например, посмотрим, что произойдет при вызове вышеприведенной функции с 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-го числа Фибоначчи:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> int fibonacci(int number) { if (number == 0) return 0; // базовый случай (условие завершения) if (number == 1) return 1; // базовый случай (условие завершения) return fibonacci(number-1) + fibonacci(number-2); } // Выводим первые 13 чисел Фибоначчи int main() { for (int count=0; count < 13; ++count) std:: cout << fibonacci(count) << " "; return 0; } |
Результат выполнения программы:
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <iostream> int factorial(int n) { if (n < 1) return 1; else return factorial(n - 1) * n; } int main() { for (int count = 0; count < 8; ++count) std::cout << factorial(count) << '\n'; } |
Задание №2
Напишите рекурсивную функцию, которая принимает целое число в качестве входных данных и возвращает сумму всех чисел этого значения (например, 482 = 4 + 8 + 2 = 14
). Протестируйте вашу программу, используя число 83569
(результатом должно быть 31
).
Ответ №2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> int sumNumbers(int x) { if (x < 10) return x; else return sumNumbers(x / 10) + x % 10; } int main() { std::cout << sumNumbers(83569) << std::endl; } |
Задание №3
Это уже немного сложнее. Напишите программу, которая просит пользователя ввести целое число, а затем использует рекурсивную функцию для вывода бинарного представления этого числа (см. урок №44). Предполагается, что число, которое введет пользователь, является положительным.
Подсказка: Используя способ №1 для конвертации чисел из десятичной системы в двоичную, вам нужно будет выводить биты «снизу вверх» (т.е. в обратном порядке), для этого ваш стейтмент вывода должен находиться после вызова рекурсии.
Ответ №3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> void printBinary(int x) { // Условие завершения if (x == 0) return; // Рекурсия к следующему биту printBinary(x / 2); // Выводим остаток (в обратном порядке) std::cout << x % 2; } int main() { int x; std::cout << "Enter an integer: "; std::cin >> x; printBinary(x); } |
Задание №4
Используя программу из задания №3, обработайте случай, когда пользователь ввел 0
или отрицательное число, например:
Enter an integer: -14
11111111111111111111111111110010
Подсказка: Вы можете конвертировать отрицательное целое число в положительное, используя оператор static_cast для конвертации в unsigned int.
Ответ №4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <iostream> void printBinaryDigits(unsigned int n) { // Условие завершения if (n == 0) return; printBinaryDigits(n / 2); std::cout << n % 2; } void printBinary(int n) { if (n == 0) std::cout << '0'; // выводим "0", если n == 0 else printBinaryDigits(static_cast<unsigned int>(n)); } int main() { int x; std::cout << "Enter an integer: "; std::cin >> x; printBinary(x); } |
Вот так сделал числа фибоначчи с помощью вектора и цикла
В тестовом задании 4 в ответе мы переводим отрицательное число в положительное и конвертируем уже положительное число в двоичную систему счисления.
А где же перевод бит в противоположные и прибавление единицы( как говорится в уроке 44)?
Всё что свыше значения положительного максимального возможного значения в signed int и есть ряд отрицательных чисел в бинарном представлении с 16-ой единицей вначале.
моя версия вычисления n-го числа Фибоначчи
я сразу о векторе подумал)) с вектором проще в коде будет))
задание №4:
мой вариант задания №4
Решил 3 задачу немного по другому, возможно более грубо, но хотелось иметь результат, который можно сразу вывести целиком.
Думал написать подобное, но размер int не позволит преобразовать число больше 1023, если использовать long long, то ограничение уходит до 1048575. Чтоб увеличить размер дальше, как я понял, можно заморочиться играми с памятью на прямую.
Фибоначчи на цикле, без рекурсии.
Более года не видел С++, забросил, писал код на Python.
Вот пришло время вернуться, повторяю/улучшаю знания по языку.
Был разговор за Фибоначчи. Рекурсивные функции.
Решил понять как работает, понял.
Отняло мин 20 на все, первый раз затупил, чуток не так было, но считало верно.
Кому интересно смотрите.
Спасибо за внимание.
В дополнение
Тут немного подправил вывод Фибоначчи и добавил алгоритм для факториала.
Код на самом деле проще не бывает, реализация простая, но работает, если кто-то хочет порекомендовать улучшение — приветствуется.
Да, вот сам код)
В общем, делюсь болью)
Не понял сначала из условия к третьему заданию что нужно выводить ответ в консоль, а не возвращать значение в коллер.
Ломал полчаса голову, писал по разному, не получалось, в итоге подсмотрел что вроде и не надо и пошёл дальше.
А теперь как лёг спать, решение начало крутиться в голове и не давать спать, как обычно, чем больше заставляешь себя думать — тем хуже получается 😀
Задание №2
Задание №3 мучелся 3 часа исписал 4 листа А4
Числа Фибоначчи итерация.
Да уж, просто пару часов собирал функцию которая у вас в одну строчку во втором задании, зато подружился с отладчиком Visual Studio)
Вопрос, почему когда вызываешь функцию, то числа Фибоначчи после 8 символов идут в периоде, а когда рекурсию то целыми числами.
4 задание.
Вроде все выполняется как надо ¯\_(ツ)_/¯
Ну отлично. Единственное что в идеале ещё добавить, так это случай когда вместо числа, введут символ.
То же самое сделал)) Вообще не очень понимаю пока что как в дальнейшем использовать рекурсию.
Немного доработал код из 1 задания.
/*Output:
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
*/
Сделал номер 4 вот так, все работает вывод такой же…
В Вашем случае при вводе пользователем 0 вывода не будет.
Приведенная рекурсивная реализация вычислений чисел Фибоначчи безумно медленная. При том, что глубина вызовов не превышает номера числа, но самих вызовов производится очень много.
Я бы на примере этой функции советовал очень аккуратно относиться к рекурсивным функциям, которые вызывают более одного своего экземпляра (эта проблема легко лечится, но само ее возникновение не так очевидно для начинающих)
По поводу цикл vs рекурсия не совсем согласен с тем, что "любую рекурсию можно реализовать циклом". Наоборот верно — "любой цикл можно заменить рекурсией"
Если пытаться оставить ту же идею и не менять ее принципиально, то в общем случае рекурсия циклом не заменяется. Иногда приходится радикально менять подход для того, чтобы переписать функцию итеративно. Это уже не "замена рекурсии на цикл", а "придумывание принципиально иного алгоритма"
На цикл однозначно и всегда заменяется "хвостовая рекурсия"
Очень простой пример: вывод последовательности в обратном порядке (последовательность читаем до 0).
рекурсивное решение:
Эту задачу легко решить итеративно, но это будет совершенно иной подход. Прочитать последовательность в какой-нить массив и затем вывести в обратном порядке.
ЗЫ Спорить о том, как лучше нет смысла. Пример приведен исключительно, чтобы показать, что "тупо в лоб" рекурсия на цикл не заменяется. Можно рассмотреть более сложные примеры из комбинаторики, для которых рекурсия простая и очевидная, а реализация решения итеративно просто выносит мозг.
Соглашусь с вами, делал свою функцию — альтернативу "itos" (int в string)
такая запись для меня оказалась на много удобней и эстетичней, чем решение ее в лоб итерацией, а это значит перебрать массив в обратном порядке. Как не крути это разные подходы к одной задаче. Но как не крути в конечном итоге когда весь основной код будет готов, можно попробовать и другие методы.
Ану переведи мне постоянный цикл, использующийся для обновления частоты экрана в рекурсию…
@@@
Поскольку функция countOut() никогда ничего не возвращает (она просто снова вызывает countOut()), то данные этой функции никогда не вытягиваются из стека!
@@@
Нет… данные не извлекаются из стека не потому, что функция ничего не возвращает… можно переписать ее код так:
и она все еще ничего не будет возвращать (да и как она что-то может вернуть, если она void? )
корректней сказать, что ни одна из функций не завершается, так как она ожидает завершения вызванной ей копии. Ну или как-то в этом роде…
Оно то понятно, что имеется в виду под "не возвращает", но для этого "понятно" нужно уже что-то знать, а тексты вроде как для новичков позиционируются 🙂
Спасибо. Так точно понятние.
ну не знаю, если человек дошел до сюда, и хорошо понимает что void не возвращает ничего, то, как по мне, можно догадаться, что имелось в виду автором, да и те кто читают уроки про рекурсию, уже явно не те новички, которыми были перед тем как прочитали эти 100 уроков
2е задание: