Как сделать рекурсию в c

Рекурсивные функции — это функции, которые вызывают сами себя. Такие функции довольно часто используются для обхода различных представлений. Например, если нам надо найти определенный файл в папке, то мы сначала смотрим все файлы в этой папке, затем смотрим все ее подпак

Например, определим вычисление факториала в виде рекурсивной функции:

#include unsigned long long factorial(unsigned); int main() < unsigned n ; auto result < factorial(n)>; std::cout unsigned long long factorial(unsigned n) < if(n >1) return n * factorial(n-1); return 1; >

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

Рекурсивная функция обязательно должна иметь некоторый базовый вариант, который использует оператор return и к которому сходится выполнение остальных вызовов этой функции. В случае с факториалом базовый вариант представлен ситуацией, при которой n = 1. В этом случае сработает инструкция return 1; .

Например, при вызове factorial(5) получится следующая цепь вызовов:

5 * factorial(4)
5 * 4 * factorial(3)
5 * 4 * 3 * factorial(2)
5 * 4 * 3 * 2 * factorial(1)
5 * 4 * 3 * 2 * 1

Другим распространенным показательным примером рекурсивной функции служит функция, вычисляющая числа Фиббоначчи. n-й член последовательности чисел Фибоначчи определяется по формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1. Значения f(0)=0 и f(1)=1, таким образом, определяют базовые варианты для данной функции:

#include unsigned long long fib(unsigned); int main() < for(unsigned i<>; i < 10; i++) < auto n = fib(i); std::cout std::cout unsigned long long fib(unsigned n)

Результат работы программы — вывод 10 чисел из последовательности Фиббоначчи на консоль:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

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

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

#include unsigned long long factorial(unsigned); int main() < unsigned n ; std::cout unsigned long long factorial(unsigned n) < unsigned long long result; for(unsigned i; i return result; >

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

Глава 1. Введение в С++
- Язык программирования С++
- Первая программа на Windows. Компилятор g++
- Первая программа на Windows. Компилятор Clang
- Первая программа на Windows. Компилятор Microsoft Visual C++
- Первая программа на Linux. Компилятор g++
- Первая программа на MacOS. Компилятор Clang
- Настройка параметров компиляции
- Локализация и кириллица в консоли
- Структура программы
- Переменные
- Типы данных
- Константы
- Ввод и вывод в консоли
- using. Подключение пространств имен и определение псевдонимов
- Арифметические операции
- Статическая типизация и преобразования типов
- Поразрядные операции
- Операции присваивания
- Условные выражения
- Конструкция if-else и тернарный оператор
- Конструкция switch-case
- Циклы
- Ссылки
- Массивы
- Многомерные массивы
- Массивы символов
- Введение в строки
- Что такое указатели
- Операции с указателями
- Арифметика указателей
- Константы и указатели
- Указатели и массивы
- Определение и объявление функций
- Область видимости объектов
- Параметры функции
- Передача аргументов по значению и по ссылке
- Константные параметры
- Оператор return и возвращение результата
- Указатели в параметрах функции
- Массивы в параметрах функции
- Параметры функции main
- Возвращение указателей и ссылок
- Перегрузка функций
- Рекурсивные функции
- Рекурсия на примере быстрой сортировки
- Указатели на функции
- Указатели на функции как параметры
- Тип функции
- Указатель на функцию как возвращаемое значение
- Разделение программы на файлы
- Внешние объекты
- Динамические объекты
- Динамические массивы
- unique_ptr
- shared_ptr
- Определение классов
- Конструкторы и инициализация объектов
- Управление доступом. Инкапсуляция
- Объявление и определение функций класса
- Конструктор копирования
- Константные объекты и функции
- Ключевое слово this
- Дружественные функции и классы
- Статические члены класса
- Деструктор
- Структуры
- Перечисления
- Наследование
- Управление доступом в базовых и производных классах
- Скрытие функционала базового класса
- Множественное наследование
- Виртуальные функции и их переопределение
- Преобразование типов
- Динамическое преобразование
- Особенности динамического связывания
- Чистые виртуальные функции и абстрактные классы
- Перегрузка операторов
- Операторы преобразования типов
- Оператор индексирования
- Переопределение оператора присваивания
- Пространства имен
- Вложенные классы
- Обработка исключений
- Вложенные try-catch
- Создание своих типов исключений
- Тип exception
- Типы исключений
- Шаблоны функций
- Шаблон класса
- Специализация шаблона класса
- Наследование и шаблоны классов
- Типы контейнеров
- Вектор
- Итераторы
- Операции с векторами
- Array
- List
- Forward_list
- Deque
- Стек std::stack
- Очередь std::queue
- Очередь приоритетов std::priority_queue
- Множества
- Словарь std::map
- Span
- Определение строк
- Строки с поддержкой Unicode
- Преобразование типов и строки
- Сравнение строк
- Получение подстроки и проверка начала и конца строки
- Поиск подстроки
- Изменение строки
- Операции с символами
- Программа подсчета слов
- Тип std:string_view
- rvalue
- Конструктор перемещения
- Оператор присваивания с перемещением
- Роль noexcept при перемещении
- Объекты функций
- Лямбда-выражения
- Захват внешних значений в лямбда-выражениях
- Шаблон std::function<>
- Минимальный и максимальный элементы
- Поиск элементов
- Копирование элементов
- Удаление элементов и идиома Remove-Erase Idiom
- Сортировка
- Представления. Фильтрация
- Проекция данных
- Пропуск элементов. drop_view и drop_while_view
- Извлечение диапазона элементов. take_view и take_while_view
- Цепочки представлений
- Оператор requires
- Концепты
- Выражение requires
- Ограничения типа для auto
- Базовые типы для работы с потоками
- Файловые потоки. Открытие и закрытие
- Чтение и запись текстовых файлов
- Переопределение операторов ввода и вывода
- Математические константы и операции
- Форматирование строк и функция format
- std::optional
- Управление ресурсами. Идиома RAII
- Идиома копирования и замены
- Идиома Move-and-Swap
- Первая программа в Visual Studio
- Первая программа в Qt Creator
Как работает рекурсия – объяснение в блок-схемах и видео

Представляю вашему вниманию перевод статьи Beau Carnes How Recursion Works — explained with flowcharts and a video.

«Для того чтобы понять рекурсию, надо сначала понять рекурсию»

Рекурсию порой сложно понять, особенно новичкам в программировании. Если говорить просто, то рекурсия – это функция, которая сама вызывает себя. Но давайте попробую объяснить на примере.

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

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

Есть два основных подхода в создании алгоритма для решения данной проблемы: итеративный и рекурсивный. Вот блок-схемы этих подходов:

Какой подход для Вас проще?

В первом подходе используется цикл while. Т.е. пока стопка коробок полная, хватай следующую коробку и смотри внутрь нее. Ниже немного псевдокода на Javascript, который отражает то, что происходит (Псевдокод написан как код, но больше похожий на человеческий язык).
```
function look_for_key(main_box) < let pile = main_box.make_a_pile_to_look_through(); while (pile is not empty) < box = pile.grab_a_box(); for (item in box) < if (item.is_a_box()) < pile.append(item) >else if (item.is_a_key()) < console.log("found the key!") >> > >
```
В другом подходе используется рекурсия. Помните, рекурсия – это когда функция вызывает саму себя. Вот второй вариант в псевдокоде:
```
function look_for_key(box) < for (item in box) < if (item.is_a_box()) < look_for_key(item); >else if (item.is_a_key()) < console.log("found the key!") >> >
```
Оба подхода выполняют одно и тоже. Основный смысл в использовании рекурсивного подхода в том, что однажды поняв, вы сможете легко его читать. В действительности нет никакого выигрыша в производительности от использования рекурсии. Порой итеративный подход с циклами будет работать быстрее, но простота рекурсии иногда предпочтительнее.

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

Граничный и рекурсивный случай

То, что Вам необходимо принять во внимание при написании рекурсивной функции – это бесконечный цикл, т.е. когда функция вызывает саму себя… и никогда не может остановиться.
Допустим, Вы хотите написать функцию подсчета. Вы можете написать ее рекурсивно на Javascript, к примеру:
```
// WARNING: This function contains an infinite loop! function countdown(i) < console.log(i) countdown(i - 1) >countdown(5); // This is the initial call to the function.
```
Эта функция будет считать до бесконечности. Так что, если Вы вдруг запустили код с бесконечным циклом, остановите его сочетанием клавиш «Ctrl-C». (Или, работая к примеру в CodePen, это можно сделать, добавив “?turn_off_js=true” в конце URL.)

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

И снова функция подсчета, только уже с граничным случаем:
```
function countdown(i) < console.log(i) if (i else < // recursive case countdown(i - 1) >> countdown(5); // This is the initial call to the function.
```
То, что происходит в этой функции может и не быть абсолютно очевидным. Я поясню, что произойдет, когда вы вызовете функцию и передадите в нее цифру 5.

Сначала мы выведем цифру 5, используя команду Console.Log. Т.к. 5 не меньше или равно 1, то мы перейдем в блок else. Здесь мы снова вызовем функцию и передадим в нее цифру 4 (т.к. 5 – 1 = 4).

Мы выведем цифру 4. И снова i не меньше или равно 1, так что мы переходим в блок else и передаем цифру 3. Это продолжается, пока i не станет равным 1. И когда это случится мы выведем в консоль 1 и i станет меньше или равно 1. Наконец мы зайдем в блок с ключевым словом return и выйдем из функции.

Стек вызовов

Рекурсивные функции используют так называемый «Стек вызовов». Когда программа вызывает функцию, функция отправляется на верх стека вызовов. Это похоже на стопку книг, вы добавляете одну вещь за одни раз. Затем, когда вы готовы снять что-то обратно, вы всегда снимаете верхний элемент.

Я продемонстрирую Вам стек вызовов в действии, используя функцию подсчета факториала. Factorial(5) пишется как 5! и рассчитывается как 5! = 5*4*3*2*1. Вот рекурсивная функция для подсчета факториала числа:
```
function fact(x) < if (x == 1) < return 1; >else < return x * fact(x-1); >> 
```
Теперь, давайте посмотрим что же происходит, когда вы вызываете fact(3). Ниже приведена иллюстрация в которой шаг за шагом показано, что происходит в стеке. Самая верхняя коробка в стеке говорит Вам, что вызывать функции fact, на которой вы остановились в данный момент:

Заметили, как каждое обращение к функции fact содержит свою собственную копию x. Это очень важное условие для работы рекурсии. Вы не можете получить доступ к другой копии функции от x.

Нашли уже ключ?

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

Но в рекурсивном подходе нет стопки. Так как тогда алгоритм понимает в какой коробке следует искать? Ответ: «Стопка коробок» сохраняется в стеке. Формируется стек из наполовину выполненных обращений к функции, каждое из которых содержит свой наполовину выполненный список из коробок для просмотра. Стек следит за стопкой коробок для Вас!

И так, спасибо рекурсии, Вы наконец смогли найти свой ключ и взять рубашку!

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

Заключение от автора

Надеюсь, что статья внесла немного больше ясности в Ваше понимание рекурсии в программировании. Основой для статьи послужил урок в моем новом видео курсе от Manning Publications под названием «Algorithms in Motion». И курс и статься написаны по замечательной книге «Grokking Algorithms», автором которой является Adit Bhargava, кем и были нарисованы все эти замечательные иллюстрации.

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

От себя хочу добавить, что с интересом наблюдаю за статьями и видеоуроками Beau Carnes, и надеюсь что Вам тоже понравилась статья и в особенности эти действительно замечательные иллюстрации из книги A. Bhargav «Grokking Algorithms».
- рекурсия
- алгоритмы
- обучение программированию
- образование
- javascript
- перевод
Простыми словами о рекурсии

В программировании рекурсия, или же рекурсивная функция — это такая функция, которая вызывает саму себя.

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

Не приведёт ли рекурсивная функция к бесконечному циклу?

Да, такой исход вполне возможен. Однако, как и у функции for или while , рекурсию можно прервать условием break , чтобы функция перестала вызывать саму себя.

Вот пример кода того, как можно реализовать функцию обратного отсчёта с использованием рекурсии:
```
function countDown(n)console.log(n)if(n > 1) countDown(n -1) // вызов рекурсии
> else return true // основное действие 
>
>
countDown(5)// 5
// 4
// 3
// 2
// 1
countDown(-1)
// - 1 // true
```
Как прервать рекурсию:

Допустим, у нас имеется функция CountDown , которая принимает аргумент (n) . Чтобы реализовать обратный отсчёт, нам следует повторить последовательность действий, понижающих значение параметра. Создадим условие вида:

Если (n) больше 1 , то вызвать функцию CountDown и вернуться в начало цикла, затем вычесть единицу и снова проверить, выполняется ли условие (n) > 1 .

По умолчанию нам нужно создать базовое условие функции, возвращающее значение true , чтобы предотвратить попадание в бесконечный цикл. Базовым условием функции здесь будет условие о том, что любое значение больше 1 не вызовет прерывание цикла.

Проще говоря, рекурсия делает то же, что и код ниже:
```
countDown(5) 
countDown(4) 
countDown(3) 
countDown(2) 
countDown(1) 
return 
return 
return 
return
return
```
Плюсы и минусы рекурсивных функций

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

Плюсы:
- Рекурсивный код снижает время выполнения функции.
Под этим подразумевается, что рекурсии, в сравнении с циклами, тратят меньше времени до завершения функции. Чем меньше строк кода у нас будет, тем быстрее функция будет обрабатывать вызовы внутри себя. Особенно хорошо это проявляется при буферизации данных, что позволяет оптимизировать и ускорить код.

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

И всё же стоит отметить, что рекурсия не всегда выигрывает по скорости по сравнению с циклами.

Многие согласятся, что эта причина очень важна. Рекурсия проста в отладке из-за того, что она не содержит сложных и длинных конструкций.

Минусы:
- Рекурсивные функции занимают много места.
Рекурсивные функции занимают значительный объём памяти во время своего выполнения. Это означает, что при каждом вызове функции в стек будет добавляться новый элемент, который будет занимать место до тех пор, пока функция не завершит работу, найдя ответ, либо пока не дойдёт до выполнения базового условия функции.
- Рекурсивные функции замедляют программу.
Несмотря на то, что уже было сказано про мемоизацию, наш код можно ускорить, если применить циклы for или while . Помимо того, что функция может быть попросту плохо написана, мы также рискуем переполнить стек, что в конечном итоге приведёт к снижению скорости и программным ошибкам.

Что такое «стек»?

Стек — это такая структура данных, которая работает по принципу «Last In, First Out» (последним пришёл — первым ушёл). Таким образом, элемент «проталкивается» в стек и добавляется в его конец, а затем «выталкивается» из стека при удалении.

Стеки замечательны тем, что они очень быстрые. Большое «О» этого алгоритма равно O(1). Такая результативность объясняется тем, что при рекурсиях не используются циклы, вместо них используются функции pop() , push() и empty() .

Стоит ли использовать рекурсии вместо обычных циклов?

Оба этих метода одинаково эффективны для решения задач, однако выбор одного из них зависит от типа проблемы, поставленной перед вами.

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

Циклы так же эффективны в плане скорости и оптимизации, они занимают меньше памяти в стеке и их легче понять, потому что в теле цикла содержится больше информации о том, что происходит внутри.
- Как освоить алгоритмы?
- Алгоритмы машинного обучения простым языком. Часть 1
- 4 принципа успешной поисковой системы и не только
Рекурсия — Основы алгоритмов и структур данных

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

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

Что такое рекурсия

Рекурсия — это вызов функции из этой же самой функции. Такое определение может показаться и простым, и непонятным одновременно. Чтобы стало понятнее, посмотрим на такую, самую простую рекурсивную функцию:
```
const f = () =>  f(); >;
```
```
def function(): function()
```
```
php function f()  f(); >
```
```
class App  public static void f()  f(); > >
```
Этот вызов будет выполняться бесконечно. Кажется, что в этом нет никакого смысла, но это не так — мы докажем это на примере. Попробуем решить такую задачу: посчитать сумму чисел от 1 до 100.

Представим, что мы уже знаем сумму чисел от 1 до 99. Тогда надо просто прибавить к ней 100:
```
sum(100) = 100 + sum(99)
```
А если мы не знаем сумму чисел от 1 до 99? Тогда нужно вычислить ее, сложив 99 и сумму чисел от 1 до 98:
```
sum(99) = 99 + sum(98)
```
По такой же логике мы будем продвигаться еще много раз. В итоге мы увидим, что программу можно свести к решению такой же задачи, но с меньшим параметром:
```
const sum = (n) =>  return n + sum(n - 1); >;
```
```
def sum(n): return n + sum(n - 1)
```
```
php function sum($n)  return $n + sum($n - 1) >
```
```
class App  public static int sum(int n)  return n + sum(n - 1); > >
```
У нас получилась рекурсивная функция. В таком виде она будет работать бесконечно: сначала параметр n уменьшается до 0, потом становится равным -1, -2 и так далее.

Нужно придумать, как остановить бесконечный вызов. Напишем код, который остановит функцию тогда, когда она дойдет до единицы. Это кажется логичным несмотря на то, что мы не можем подсчитать сумму чисел от 1 до 1. Мы берем число 1, и ни с чем его не складываем:
```
sum(1) = 1
```
У нас получается рекурсивная функция sum :
```
const sum = (n) =>  if (n === 1)  return 1; > return n + sum(n - 1); >; sum(100) // 5050
```
```
def sum(n): if n == 1: return 1 return n + sum(n - 1) sum(100) # 5050
```
```
php function sum($n)  if ($n === 1)  return 1; > return $n + sum($n - 1); >; sum(100); // 5050
```
```
class App  public static int sum(int n)  if (n == 1)  return 1; > return n + sum(n - 1); > > App.sum(100); // 5050
```
Теперь рекурсивная функция остановится после ста вызовов и вычислит сумму чисел от 1 до 100.

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

Рекурсия вместо цикла

Один из распространенных алгоритмов в программировании — это бинарный поиск, который мы уже изучали в этом курсе. Мы уже рассмотрели его реализацию через циклы:
```
const binarySearch = (items, value) =>  let left = 0; let right = items.length - 1; while (left  right)  const middle = Math.floor((left + right) / 2); if (value == items[middle])  return middle; > if (value  items[middle])  right = middle - 1; > else  left = middle + 1; > > return -1; >; const items = [-3, -1, 1, 3, 5, 7, 9, 11]; console.log(binarySearch(items, 100)); // => -1 console.log(binarySearch(items, -1)); // => 1 console.log(binarySearch(items, 7)); // => 5
```
```
def binary_search(items, value): left = 0 right = len(items) - 1 while (left  right): middle = (left + right) // 2 if value == items[middle]: return middle if value  items[middle]: right = middle - 1 else: left = middle + 1 return -1 items = [-3, -1, 1, 3, 5, 7, 9, 11] print(binary_search(items, 100)) # => -1 print(binary_search(items, -1)) # => 1 print(binary_search(items, 7)) # => 5
```
```
php function binarySearch($items, $value)  $left = 0; $right = count($items) - 1; while ($left  $right)  $middle = round(($left + $right) / 2); if ($value === $items[$middle])  return $middle; > if ($value  $items[$middle])  $right = $middle - 1; > else  $left = $middle + 1; > > $return -1; > $items = [-3, -1, 1, 3, 5, 7, 9, 11]; print_r(binarySearch($items, 100)); // => -1 print_r(binarySearch($items, -1)); // => 1 print_r(binarySearch($items, 7)); // => 5
```
```
class App  public static int binarySearch(ListInteger> items, int value)  var left = 0; var right = items.size() - 1; while (left  right)  var middle = (left + right) / 2; if (value == items.get(middle))  return middle; > if (value  items.get(middle))  right = middle - 1; > else  left = middle + 1; > > return -1; > > ListInteger> items = List.of(-3, -1, 1, 3, 5, 7, 9, 11); App.binarySearch(items, 100); // -1 App.binarySearch(items, -1); // 1 App.binarySearch(items, 7); // 5
```
Тогда мы описывали алгоритм через циклы, поэтому объяснение было подробным и сложным. Алгоритм бинарного поиска можно описать намного проще, если опираться на знания о рекурсии:
1. Если массив пустой, то поиск завершается неудачно
2. Если массив не пустой, сравниваем наш элемент со средним элементом массива. Если они равны, поиск завершается удачно
3. Если средний элемент больше нужного, повторяем поиск в левой половине массива
4. Если средний элемент меньше нужного, повторяем поиск в правой половине массива
И это все: мы свели задачу поиска к самой себе. Сначала зона поиска — это весь массив, но на каждом шаге она сужается в два раза. Если нужного элемента в массиве не окажется, зона поиска сузится до пустого массива, и поиск завершится неудачно:
```
const binarySearch = (items, value, left, right) =>  if (left > right)  return -1; > const middle = Math.floor((left + right) / 2); if (value == items[middle])  return middle; > if (value  items[middle])  return binarySearch(items, value, left, middle - 1); > return binarySearch(items, value, middle + 1, right); >; const items = [-3, -1, 1, 3, 5, 7, 9, 11]; console.log(binarySearch(items, 100, 0, items.length - 1)); // => -1 console.log(binarySearch(items, -1, 0, items.length - 1)); // => 1 console.log(binarySearch(items, 7, 0, items.length - 1)); // => 5
```
```
def binary_search(items, value, left, right): if left > right: return -1 middle = (left + right) // 2 if value == items[middle]: return middle if value  items[middle]: return binary_search(items, value, left, middle - 1) return binary_search(items, value, middle + 1, right) items = [-3, -1, 1, 3, 5, 7, 9, 11] print(binary_search(items, 100, 0, len(items) - 1)) # => -1 print(binary_search(items, -1, 0, len(items) - 1)) # => 1 print(binary_search(items, 7, 0, len(items) - 1)) # => 5
```
```
php function binarySearch($items, $value, $left, $right)  if ($left > $right)  return -1; > $middle = round(($left + $right) / 2); if ($value === $items[$middle])  return $middle; > if ($value  $items[$middle])  return binarySearch($items, $value, $left, $middle - 1); > return binarySearch($items, $value, $middle + 1, $right); > $items = [-3, -1, 1, 3, 5, 7, 9, 11]; print_r(binarySearch($items, 100, 0, count($items) - 1)); // => -1 print_r(binarySearch($items, -1, 0, count($items) - 1)); // => 1 print_r(binarySearch($items, 7, 0, count($items) - 1)); // => 5
```
```
class App  public static int binarySearch(ListInteger> items, int value, int left, int right)  if (left > right)  return -1; > var middle = (left + right) / 2; if (value == items.get(middle))  return middle; > if (value  items.get(middle))  return binarySearch(items, value, left, middle - 1); > return binarySearch(items, value, middle + 1, right); > > ListInteger> items = List.of(-3, -1, 1, 3, 5, 7, 9, 11); App.binarySearch(items, 100, 0, items.size() - 1); // -1 App.binarySearch(items, -1, 0, items.size() - 1); // 1 App.binarySearch(items, 7, 0, items.size() - 1); // 5
```
Как видно на примере выше, рекурсивный алгоритм очень похож на итерационный — то есть сделанный с помощью цикла. Но его гораздо проще объяснять не через циклы, а через рекурсию.

Продолжим изучать рекурсию на еще одном примере.

Рекурсивный алгоритм для Ханойской башни

Ханойская башня — это знаменитая древняя головоломка. Она состоит из трех стержней, на один из которых надеты кольца разного размера.

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

Попробуем спроектировать алгоритм, который решит эту головоломку. Для начала формализуем задачу:
- Обозначим стержни числами 1, 2 и 3
- Определимся, что нам нужен универсальный алгоритм, который решает головоломку при любой высоте башен
- Назовем функцию hanoi и зададим ей три параметра:
1. Количество колец (высота башни, которую мы хотим перенести)
2. Номер стержня, откуда мы будем переносить башню
3. Номер стержня, куда мы будем переносить башню
Таким образом, вызов hanoi(10, 1, 3) будет означать: «Перенести башню из десяти колец с первого стержня на третий».

Функция должна печатать последовательность переносов: взять верхнее кольцо со стержня №1 и перенести его на стержень №2. Мы не можем взять второе сверху кольцо или пятое сверху — только самое верхнее. Поэтому нам достаточно просто выводить номера обоих стержней: откуда снимать кольцо и куда переносить.

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

Здесь на помощь приходит рекурсия. Попробуем упростить задачу и свести ее к самой себе:
- Предположим, что мы уже умеем переносить башню из четырех колец
- Дальше нам надо перенести башню из пяти с первого стержня на второй
- Воспользуемся третьим стержнем и перенесем на него четыре верхних кольца
- Теперь можем взять самое большое кольцо с первого стержня и перенести его на пустой второй
- Осталось снять башню из четырех колец со вспомогательного третьего стержня и перенести ее на второй стержень, на котором уже лежит большое пятое кольцо второго стержня — это мы уже умеем
Можно ли будет класть какие-то кольца поверх самого большого пятого? Да, потому что правила запрещают только класть большие кольца на меньше, а наоборот — нет. Оказывается, что этих рассуждений достаточно, чтобы написать рекурсивную функцию.

Только мы знаем, что рекурсия должна где-то останавливаться. В нашем случае минимальная задача, которую мы можем решить — перенос башни из одного кольца. Она решается тривиально: одно кольцо мы можем перенести безо всяких условий, поэтому нам достаточно просто вывести номера стержней «откуда» и «куда»:
```
const hanoi = (height, from, to) =>  if (height === 1)  console.log("с %d на %d", from, to); return; > const temporary = 6 - from - to; hanoi(height - 1, from, temporary); console.log("с %d на %d", from, to); hanoi(height - 1, temporary, to); >; hanoi(4, 1, 2); // => с 1 на 3 // => с 1 на 2 // => с 3 на 2 // => с 1 на 3 // => с 2 на 1 // => с 2 на 3 // => с 1 на 3 // => с 1 на 2 // => с 3 на 2 // => с 3 на 1 // => с 2 на 1 // => с 3 на 2 // => с 1 на 3 // => с 1 на 2 // => с 3 на 2
```
```
def hanoi(height, start, to): if height == 1: print(f'с start> на to>') return temporary = 6 - start - to hanoi(height - 1, start, temporary) print(f'с start> на to>') hanoi(height - 1, temporary, to) hanoi(4, 1, 2) # => с 1 на 3 # => с 1 на 2 # => с 3 на 2 # => с 1 на 3 # => с 2 на 1 # => с 2 на 3 # => с 1 на 3 # => с 1 на 2 # => с 3 на 2 # => с 3 на 1 # => с 2 на 1 # => с 3 на 2 # => с 1 на 3 # => с 1 на 2 # => с 3 на 2
```
```
php function hanoi($height, $from, $to)  if ($height === 1)  print_r("с $from> на $to>\n"); return; > $temporary = 6 - $from - $to; hanoi($height - 1, $from, $temporary); print_r("с $from> на $to>\n"); hanoi($height - 1, $temporary, $to); > hanoi(4, 1, 2); // => с 1 на 3 // => с 1 на 2 // => с 3 на 2 // => с 1 на 3 // => с 2 на 1 // => с 2 на 3 // => с 1 на 3 // => с 1 на 2 // => с 3 на 2 // => с 3 на 1 // => с 2 на 1 // => с 3 на 2 // => с 1 на 3 // => с 1 на 2 // => с 3 на 2
```
```
class App  public static void hanoi(int height, int from, int to)  if (height == 1)  System.out.println(String.format("с %d на %d", from, to)); return; > var temporary = 6 - from - to; hanoi(height - 1, from, temporary); System.out.println(String.format("с %d на %d", from, to)); hanoi(height - 1, temporary, to); > > App.hanoi(4, 1, 2); // => с 1 на 3 // => с 1 на 2 // => с 3 на 2 // => с 1 на 3 // => с 2 на 1 // => с 2 на 3 // => с 1 на 3 // => с 1 на 2 // => с 3 на 2 // => с 3 на 1 // => с 2 на 1 // => с 3 на 2 // => с 1 на 3 // => с 1 на 2 // => с 3 на 2
```
Удивительно, что этот алгоритм казался сложным на словах, но в коде получился таким простым. Здесь мы применили один трюк, который помогает упростить код. Разберем его подробнее.

Во время работы алгоритма стержни постоянно меняются ролями. Например, если мы хотим перенести башню с первого стержня на третий, то второй стержень выступает как вспомогательный — туда мы перенесем все кольца, кроме нижнего. А если мы переносим маленькую башню с первого стержня на второй, то роль вспомогательного переходит третьему стержню.

Чтобы определить номер вспомогательного стержня, надо написать сложное условие:
```
if (from === 1 && to === 2 || from === 2 && to === 1)  temporary = 3; > else if (from === 2 && to === 3 || from === 3 && to === 2)  temporary = 1; > else if (from === 1 && to === 3 || from === 3 && to === 1)  temporary = 2; >
```
```
if (start == 1 and to == 2) or (start == 2 and to == 1): temporary = 3 elif (start == 2 and to == 3) or (start == 3 and to == 2): temporary = 1 elif (start == 1 and to == 3) or (start == 3 and to == 1): temporary = 2
```
```
php if ($from === 1 && $to === 2 || $from === 2 && $to === 1)  $temporary = 3; > else if ($from === 2 && $to === 3 || $from === 3 && $to === 2)  $temporary = 1; > else if ($from === 1 && $to === 3 || $from === 3 && $to === 1)  $temporary = 2; >
```
```
if (from == 1 && to == 2 || from == 2 && to == 1)  temporary = 3; > else if (from == 2 && to == 3 || from == 3 && to == 2)  temporary = 1; > else if (from == 1 && to == 3 || from == 3 && to == 1)  temporary = 2; >
```
Несмотря на то, что логика этого кода понятна, само условие выглядит громоздким. Разберем по шагам, как оно работает. В коде используют три константы:
- from — номер стержня, с которого мы перемещаем кольца
- to — номер стержня, на который мы хотим переместить наши кольца
- temporary — номер стержня, который мы используем для временного хранения первых n-1 дисков
Еще в вызове указано количество колец — высота башни, которую мы хотим перенести. Таким образом, вызов hanoi(n, 1, 3) будет означать: «Перенести башню из n колец с первого стержня на третий».

Обратите внимание, что сумма from , to и temporary всегда равна 6. Можно взять число 6 и вычесть из него номера стержней from и to , и тогда мы узнаем номер вспомогательного стержня:
```
const temporary = 6 - from - to;
```
```
temporary = 6 - start - to
```
```
php $temporary = 6 - $start - $to;
```
```
var temporary = 6 - from - to;
```
Этот код гораздо проще, но требует разъяснений. В начале каждой рекурсивной функции мы должны проверить граничное условие — оно помогает не войти в бесконечный вызов. В задаче о ханойской башне граничное условие — это башня из одного кольца.

Если встретилась такая башня, надо перенести кольцо и завершить работу:
```
if (height === 1)  console.log("с %d на %d", from, to); return; >
```
```
if height == 1: print(f'с start> на to>') return
```
```
php if ($height === 1)  print_r("с $from> на $to>"); return; >
```
```
if (height == 1)  System.out.println(String.format("с %d на %d", from, to)); return; >
```
Если высота башни height больше единицы, мы упрощаем задачу и сводим ее к самой себе. В случае ханойской башни такая задача — перенести башни высотой height — 1 на вспомогательный стержень. После этого можно перенести самое большое кольцо на стержень «куда», а потом — переместить на него маленькую башню со вспомогательного стержня:
```
hanoi(height - 1, from, temporary); console.log("с %d на %d", from, to); hanoi(height - 1, temporary, to);
```
```
hanoi(height - 1, start, temporary) print(f'с start> на to>'); hanoi(height - 1, temporary, to)
```
```
php hanoi($height - 1, $from, $temporary); print_r("с $from> на $to>"); hanoi($height - 1, $temporary, $to);
```
```
hanoi(height - 1, from, temporary); System.out.println(String.format("с %d на %d", from, to)); hanoi(height - 1, temporary, to);
```
Достоинства и недостатки рекурсии

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

Еще один плюс — знания о рекурсии открывают программисту новые возможности. Многие задачи можно решить и с помощью циклов, но есть и те, в которых не обойтись без рекурсии. Например, синтаксический разбор арифметических выражений можно сделать только рекурсивно. Вот так выглядит сложное арифметическое выражение, если решать его через рекурсивный алгоритм:
```
sin(a) + (3 + 2 * b ** 7 - cos (a / b))
```
К недостаткам рекурсивных решений относят потребление памяти. При каждом вызове функции компьютер тратит память на передачу параметров, а также сохраняет адрес следующей инструкции — чтобы понимать, откуда продолжить выполнение программы, когда функция завершится. Большое количество рекурсивных вызовов может привести к исчерпанию памяти.

Компьютер сохраняет данные в специальной области, которая называется стек. Когда вся память исчерпана, возникает ошибка переполнения стека. По-английски эта ошибка называется stack overflow. В честь этой ошибки назван сайт stackoverflow.com, где программисты отвечают на вопросы друг друга об ошибках в их программах.

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

Выводы
- Рекурсия — важный прием в программировании. Она используется при проектировании алгоритмов и помогает решать задачи, которые невозможно решить другим способом
Похожие публикации: