Реальные примеры с кодом
«Чтобы понять рекурсию, нужно сначала понять рекурсию. «И как только вы поймете рекурсию, все готово…😃😃
Рекурсия происходит непосредственно из математики, где есть много примеров выражений, записанных в терминах самих себя. Например, последовательность Фибоначчи определяется как:
F(i) = F(i-1) + F(i-2).
Или факториал последовательность определяется как:
n! = п * (п — 1) * (п — 2) * (п — 3) ….
✨ Что такое рекурсия в программировании?
В терминах программированиярекурсия – это функция, вызывающая сама себя, пока "базовое условие" не станет правильным выводом.
Другими словами: для решения проблемы. , мы решаем проблему, которая является меньшим экземпляром той же проблемы, а затем используем решение этого меньшего экземпляра для решения исходной проблемы.
👩🏻🦰 : о, понял. Но что такое рекурсивная функция?😕
🔸 Функция, которая вызывает сама себя, называется рекурсивной функцией. и этот метод известен как рекурсия.
Чтобы рекурсивный алгоритм работал, меньшие подзадачи должны в конечном итоге прийти к базовому случаю. Проще говоря, любой рекурсивный алгоритм состоит из двух частей:
Часть 1: Базовый случай: завершающее условие, при котором функция может немедленно вернуть результат. Это наименьшая версия задачи,для которой мы уже знаем решение.
Часть 2. Рекурсивная структура: Разработка решения к проблеме через решение ее более мелких подзадач, т.е. той же проблемы, но для меньшего размера ввода. Мы продолжаем вызывать ту же проблему для меньших размеров входных данных, пока не достигнем базового условия рекурсии.
🧿Теория скучна, правда? нам нужен пример из реальной жизни…
Например, мы можем определить операцию как:
«найди дорогу к дому своей девушки»😜
🔸 Если ты уже у своей подруги домой, перестань двигаться.
🔸 Если нет, попробуй найти ее дом и сделай шаг к дому.
Здесь решение найти дорогу домой состоит из двух шагов (фактически трех шагов). Во-первых, мы не идем домой, если мы уже дома.
Во-вторых, мы делаем очень простой шаг, который упрощает решение нашей ситуации. Наконец мы повторяем весь алгоритм.
Как бы вы написали рекурсивный «алгоритм» поиска торгового центра?
Функция «Найти торговый центр»:
шаг 1: Спросите кого-нибудь, куда идти. (они указывают на «это подальше»)
Шаг 2: Отодвиньте «это подальше», пока не станете уверены
Шаг 3: Найдите торговый центр. (переделать весь алгоритм)
✨ Еще один пример рекурсии в реальной жизни:
Предположим, вы стоите в длинной очереди людей. Сколько человек стоит прямо за вами в очереди?
Условие:
🔸 один человек может видеть только человека, стоящего прямо спереди и сзади. Так что нельзя просто оглянуться и сосчитать.
🔸Каждому человеку разрешено задавать вопросы тому, кто стоит спереди или сзади.
Как мы можем решить эту задачу рекурсивно?
Решение:
🔸 вы оглядываетесь назад и видите, есть ли там человек. если нет, то можно вернуть ответ «0». если есть человек, повторите этот шаг и дождитесь ответа от человека, стоящего позади.
🔸 Как только человек получает ответ, он добавляет 1 для человека позади него и отвечает тому, кто его спросил, или человек, стоящий перед ними.
Пришло время взять простую и популярную задачу и решить ее с помощью рекурсии…
✨ Давайте попробуем понять рекурсию с помощью нахождения n-го факториала:
факториал, в математике произведение всех положительных целых чисел, меньших или равных заданному положительному целому числу и обозначаемое этим целым числом и восклицательным знаком.
факториал Десять пишется 10! что означает 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10.
Факториал Девять записывается как 9! означает 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9.
факториал Восемь пишется как 8! что означает 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8.
Факториал Семь записывается как 7! что означает 1 × 2 × 3 × 4 × 5 × 6 × 7.
Факториал Шесть записывается как 6! что означает 1 × 2 × 3 × 4 × 5 × 6.
Факториал Пять записывается как 5! что означает 1 × 2 × 3 × 4 × 5.
посмотрите на приведенный выше пример:
5! = 1 × 2 × 3 × 4 × 5.
6! = 1 × 2 × 3 × 4 × 5× 6.
или можно сказать так:
6! = 6× факториал 5
или
6! = 6 × 5!
Еще раз:
6! = 1 × 2 × 3 × 4 × 5 × 6.
7! = 1 × 2 × 3 × 4 × 5 × 6× 7.
или можно сказать, что:
7! = 7 × факториал 6
или
7! = 7 × 6!
Теперь, каков факториал n?
мы можем написать: n! = n × (n-1)-й факториал
или, n! = п × (п-1)!
Если мы вычислим значение (n-1)-го факториала, мы сможем легко вычислить значение n-го факториала.
Это означает, что мы можем решить проблему размера входных данных n с меньшей проблемой размера входных данных (n-1).
Другими словами, мы можем решить эту проблему, используя идею рекурсии!
Предположим, у нас есть функция с именем factorial,функция factorial(n) и factorial(n-1) вернуть значение n-го и (n-1)-го факториала,
тогда мы можем написать следующую рекурсивную структуру:
factorial(n) = n × factorial(n-1)
🔥Теперь давайте погрузимся в код:🔥
Вот рекурсивнаяфункция для вычисления n-го факториала
function factorial(n){ //base case if(n == 0 || n == 1){ return 1; //recursive case } else{ return n * factorial(n-1); } };
Та же проблему можно решить с помощью обычного цикла for:
function factorial(n){ let answer = 1; if (n == 0 || n == 1){ return answer; }; else{ for(var i = n; i >= 1; i--){ answer = answer * i; }; return answer; }; };
За: занимает меньше памяти, чем рекурсивная реализация.
Против: код длиннее, чем код рекурсивной реализации.
🧿 Вот еще одна рекурсивная функция для вычисления n-гоФибоначчи:
последовательность определяется как:
F(i) = F(i-1) + F(i-2).
function fibonacci(num) { if(num < 2) { return num; } else { return fibonacci(num-1) + fibonacci(num - 2); } }
✨Как рекурсия работает в фоновом режиме?
Если мы нарисуем поток рекурсии для приведенной выше факториальной программы, можно обнаружить такую закономерность: мы вызываем factorial(0) в последнюю очередь, но она возвращает значение первой. Точно так же мы сначала вызываем factorial(n), но он возвращает значение последним.
Вы заметили, что Last In First Out (LIFO) пахнет рекурсивными вызовами и возвращаемыми значениями?
Да, вы поняли! За кулисами компилятор использует структуру данных стека для имитации рекурсии и получения правильного вывода. Мы называем этот стек:
Стек вызовов!
🔸 Порядок рекурсивных вызовов: от большей проблемы к меньшей
factorial(n) -> factorial(n — 1) -> … -› factorial(i) -> … -› factorial( 1) -> факториал(0)
🔸 Порядок возвращаемых значений: от меньшей проблемы к большей проблеме
factorial(0) -> factorial(1) -> …-> factorial(i) -> … -> factorial(n — 1) -> факториал(n)
Позже я напишу отдельную статью о стеке вызовов. стек вызовов заслуживает этого.
Ну, на сегодня все. Я надеюсь, что это руководство поможет вам понять рекурсию. Если у вас есть какие-либо вопросы или сомнения по поводу этого руководства, не стесняйтесь, дайте мне знать…
удачного программирования. эм>💕