Рекурсия в программировании: понятие, суть, примеры

Чтобы понять рекурсию, нужно понять рекурсию. В этой шутке — вся суть понятия, но попробуем всё-таки разобрать его подробно.

  • Что такое рекурсия в программировании
  • Плюсы и минусы рекурсивных функций
  • Как прервать рекурсию
  • Примеры алгоритмов рекурсии в программировании
  • Совет от эксперта

Что такое рекурсия в программировании 

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

Внутри кода это может выглядеть так:

func А (x) => x * A(x-1)

Понятие рекурсии используется только в программировании и иногда в мемах

Иногда рекурсия бывает косвенной. Например, функция А вызывает функцию В, а В — А. В итоге из А всё равно возвращаемся к А, хотя напрямую вызова самой себя в функции не происходит.

Пример косвенной рекурсии с сайта Lurkmore

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

Вот как будет выглядеть код такой функции на Python:

Если передать число 3, то она последовательно выведет 3, 2, 1. Внутри функции A также вызывают функцию A — это и есть рекурсия.

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

Любую рекурсивную функцию можно описать в виде цикла, так что теоретически рекурсии можно не использовать в коде вообще. Однако у них есть преимущества перед циклами.

Материал по теме:

Что такое парадигмы программирования и зачем они нужны

Плюсы и минусы рекурсивных функций

● Часто код с рекурсией короче и проще, чем код цикла. Это облегчает его написание и понимание другими разработчиками.

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

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

Минусы

● Нередко требует больше времени на выполнение, если число строк в рекурсии и аналогичном цикле не различается на порядки. Это может быть важно для программ, которые должны работать максимально быстро, — например, для аналитики больших объёмов данных в реальном времени.

● Может переполнить память. При каждом вызове рекурсивная функция добавляется в специальный стек, место в котором ограничено. Если вызовов окажется слишком много, память программы переполнится, что приведёт к ошибке.

● Если забыть прописать условие выхода, рекурсия будет выполняться бесконечно — программу придётся завершать принудительно.

Принцип «Разделяй и властвуй» — самое популярное и частое применение для рекурсии. Декомпозиция, то есть разбиение любой задачи на более мелкие части, — основа, на которой строится принцип рекурсии:

1. Разделять.
Решать проблему напрямую, если она небольшая. В противном случае разделить задачу на меньшие подмножества той же проблемы.

2. Властвовать.
Решать меньшие задачи рекурсивно. Если подзадача достаточно мала, рекурсия не нужна и можно решить её напрямую.

3. Комбинировать.
Взять готовое решение для маленькой подзадачи и объединить с решением исходной проблемы.

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

Как прервать рекурсию

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

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

Здесь есть условие — if(n>=1). Только в этом случае функция продолжает вызывать саму себя и что-то выводит. Как только n становится меньше единицы, функция прекращается, и рекурсия останавливается.

Чтобы прервать рекурсию, нужно:

  1. Прописать условие выхода из рекурсии до повторного вызова функции, иначе это условие просто не успеет пройти проверку. Обычно условие прописывают с помощью конструкции if.
  2. Убедиться, что это условие будет достигнуто. Например, если прописать if(n>=1), но не вычитать из n единицу, а прибавлять её, условие никогда не наступит, и рекурсия станет бесконечной.

Если код запущен, но что-то пошло не так и код не останавливается из-за рекурсии, его нужно остановить принудительно. Способ сделать это зависит от среды, в которой запущен код. Например, в терминале Windows для этого обычно нужно нажать Ctrl+C на клавиатуре.

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

Рекурсию можно использовать, чтобы:

● посчитать количество определённых символов в строке;

● определить какое-то свойство числа, например чётность или простоту;

● вычислить произведение нескольких чисел, возведение в степень, факториал;

● найти длину списка;

● перевести число в другую систему счисления;

● определить максимальный или минимальный элемент списка;

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

Возьмём пример кода на Python — возведение числа x в степень y. Функция должна уметь принимать оба значения и возводить первое число в степень, равную второму числу.


Вот как будет выглядеть его псевдокод — упрощённый, более понятный для чтения:

Что здесь происходит:

  1. Проверка, не введён ли 0 как значение степени: в этом случае сразу выводится 1, так как любое число в степени 0 равно 1.
  2. Создание условие выхода из рекурсии: как только y достигает 1, умножение прекращается и возвращается x, поскольку любое число в степени 1 равно самому себе.
  3. Рекурсивное умножение x на само себя столько раз, сколько задано в переменной y.
  4. Вывод результата возведения в степень.

Ещё один пример — подсчёт длины коллекции. Вот как будет выглядеть его псевдокод:

Что здесь происходит:

  1. Создание условия выхода из рекурсии — если длина коллекции равна нулю, работа функции прекращается.
  2. Создание счётчика — начинается с 1 и рекурсивно прибавляется к ней ещё по 1, что постепенно отрезает от коллекции по одному элементу. Это делается с помощью среза коллекции collection[1:].
  3. Создание коллекции n из 5 элементов. Здесь она задаётся фиксированно, но в реальном коде коллекция может пополняться постепенно, и её длину действительно понадобится посчитать.
  4. Вывод длины коллекции путём передачи списка в качестве аргумента функции.
  5. Получение результата 5.

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

Что здесь происходит:

  1. Создание условия выхода из рекурсии — как только количество чисел в последовательности становится 1.
  2. Сложение введённого числа, уменьшенного на единицу, с введённым числом, уменьшенным на два.
  3. Запрос у пользователя, сколько чисел Фибоначчи он хочет получить.
  4. Запуск вывода в виде цикла до тех пор, пока счётчик i не достигнет значения n.

Совет от эксперта

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

Научитесь писать понятный и поддерживаемый код

А ещё видеть разные варианты решения задачи и сравнивать их по эффективности. Курс «Алгоритмы и структуры данных» выведет на новый профессиональный уровень тех, кто уверенно владеет C++, Python, Java, Go, JavaScript или C#.

Статью подготовили:

Поделиться

Читать также:

Фронтенд или бэкенд: по какому пути в разработке пойти

Читать статью

Как установить Python и начать на нём писать

Читать статью

Косвенная рекурсия — Большая Энциклопедия Нефти и Газа, статья, страница 1

Cтраница 1

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

В случае косвенной рекурсии возникает проблема: как и где описать вызываемый модуль.  [2]

Все сказанное выше будет также верно и для так называемой косвенной рекурсии — когда подпрограмма А вызывает подпрограмму В, а в В содержится вызов А.  [3]

Алгоритм рисования кривых Серпинского, представленный ранее, включает в себя и множественную, и косвенную рекурсию. Поскольку алгоритм состоит из четырех подпрограмм, которые вызывают друг друга, нельзя просто пронумеровать важные строки программы, как в случае с алгоритмом Гильбертовых кривых.  [4]

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

 [5]

В, являющейся копией объекта С, имеющего в качестве компоненты указанное выше имя А. Иными словами, исключается косвенная рекурсия в определениях.  [6]

Методы, описанные в предыдущем разделе, используются, когда алгоритм содержит многократную или косвенную рекурсию.  [7]

В рассмотренных выше случаях процедуры или функции вызывали себя сами, это называется прямой рекурсией. Кроме того, процедура Р может вызывать процедуру Q, которая в свою очередь вызывает процедуру Р: это называется косвенной рекурсией. Ниже приведен пример, в котором используется косвенная рекурсия.  [8]

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

 [9]

Тот факт, что АЛГОЛ допускает рекурсию, вызван разнообразными причинами, поскольку нужда в рекурсии при решении задач численного анализа не столь очевидна. Некоторые приверженцы АЛГОЛа утверждают, что наличие рекурсии является его основным преимуществом перед другими языками типа ФОРТРАНа. Хотя это утверждение и справедливо для рекурсивно определенных функций, оно неверно для рекурсивного использования процедур ( иногда называемого косвенной рекурсией), которое, как мы видели, имеет важное значение для численного анализа.  [10]

Тот факт, что АЛГОЛ допускает рекурсию, вызван разнообразными причинами, поскольку нужда в рекурсии при решении задач численного анализа не столь очевидна. Некоторые приверженцы АЛГОЛа утверждают, что наличие рекурсии является его основным преимуществом перед другими языками типа ФОРТРАНа. Хотя это утверждение и справедливо для рекурсивно определенных функций, оно неверно для рекурсивного использования процедур ( иногда называемого

косвенной рекурсией), которое, как мы видели, имеет важное значение для численного анализа.  [11]

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

многократной и косвенной рекурсией. Каждая из этих процедур вызывает себя и три другие процедуры до четырех раз.  [12]

Функция может вызывать самое себя. Это называется рекурсией, которая может быть прямой или косвенной. Когда функция вызывает самое себя, речь идет о прямой рекурсии. Если же функция вызывает другую функцию, которая затем вызывает первую, то в этом случае имеет место косвенная рекурсия.  [13]

Страницы:      1

Рекурсия стала проще. Любой, кто читает структуры данных и… | Прерит Субраманья | Аналитика Vidhya

  1. Рекурсия стала проще

Любой, кто читает структуры данных и алгоритмы, сталкивался с темой под названием «Рекурсия». Вот лучший способ понять рекурсию. Прочтите это несколько раз, пока ваше понимание не станет «Истинным» . Ха-ха!! вот насколько проста рекурсия.

Ну, рекурсия может быть реализована на любом языке и имеет тот же результат. Здесь я продемонстрирую несколько тем и ключевых концепций рекурсии в python🐍. Да, вы правильно прочитали, одна любовь к питону❤.

Функция, вызывающая саму себя до тех пор, пока условие не станет истинным или ложным, называется рекурсивной функцией. На изображении ниже показана простая функция под названием «recursive_fun», вызывающая сама себя «n» раз.

простой пример рекурсии

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

дерево трассировки recursive_fun (прямая фаза)

приведенное выше дерево трассировки многое объясняет о том, как происходит повторяющийся вызов функции для получения желаемого результата. Здесь recursive_fun вызывается 3+1 раз, где для всех 3 раз он печатает ‘n’, но для последнего вызова он не удовлетворяет условию и возвращает 0. Следовательно, в любой рекурсии вызов функции выполняется n+1 раз. Кроме того, внимательно наблюдая за деревом трассировки, мы видим, что recursive_fun выполняет оператор печати перед вызовом самого себя, это называется опережающей фазой. Обратная фаза рекурсии — это когда функция вызывает себя перед выполнением каких-либо операторов, т. е. все остальные операторы выполняются до тех пор, пока не прекратятся дальнейшие вызовы функций.

обратная фазовая рекурсия

На приведенном выше изображении ясно показано, как выход изменяется с 3 2 1 до 1 2 3 в обратной фазе. Это связано с тем, что вызов функции происходит перед оператором печати, в то время как оператор печати выполняется в возвратной или обратной фазе или, другими словами, когда recursive_fun(0) выходит за пределы области действия. Оператор печати recursive_fun(1) выполняется, а затем выходит из области видимости. . Это продолжается до тех пор, пока весь вызов функции не выйдет за пределы области видимости.

Дерево трассировки для обратной фазовой рекурсии, оператор печати выполняется, как показано стрелками

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

расчет временной сложности с использованием дерева трассировки

, следовательно, из приведенного выше рисунка для n = 3; t(n) = O(1)+O(1)+O(1)+O(1) = O(4). Мы можем сделать вывод для n = 3 как O (3 + 1), т. Е. Для n временная сложность равна O (n).

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

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

Использование стека функции рекурсии в циклах

, как показано, для n = 3 создаются 4 записи активации, т. е. для каждого вызова в стеке создается новая запись активации, использующая больше памяти, чем цикл for или while.

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

Хвостовая рекурсия:

Функция рекурсии, которая выполняет все операции или операторы перед вызовом самой себя, называется хвостовой рекурсией. Здесь функция определяется таким образом, что некоторые операции или выполнение операторов ввода-вывода выполняются непосредственно перед вызовом самой себя, или вызов функции самому себе является последней операцией в потоке кода. В хвостовой рекурсии мы наблюдаем прямую фазу рекурсии.

Хвостовая рекурсия

Головная рекурсия:

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

Головная рекурсия

Древовидная рекурсия:

Древовидная рекурсия — это когда вызов функции к самой себе выполняется более одного раза. Здесь мы наблюдаем как прямую, так и обратную фазу, поскольку первый вызов функции устанавливается в значение true, а второй вызов функции вызывается при возврате или в обратной фазе.

Tree recursionТрассировка дерева для рекурсии дерева

изображение дерева трассировки для функции рекурсии дерева, где n = 3, объясняет, как достигается результат «3 2 1 1 2 1 1».

Косвенная рекурсия:

Когда две функции говорят, что «funA» и «funB» имеют взаимный вызов друг к другу до тех пор, пока условие не будет выполнено или не будет установлено значение true/false, это называется косвенной рекурсией.

Косвенная рекурсия Дерево трассировки косвенной рекурсии

В приведенном выше примере есть две функции «recursive_fun()» и «recursive_fun1()» соответственно, которые имеют взаимные вызовы друг друга, ведущие к косвенной рекурсии. Обратите внимание, что значение «n» просто передается одной функции.

Вложенная рекурсия:

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

Дерево вложенной рекурсииTracing для вложенной рекурсии

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

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

Ответ: Рекурсия может быть прямой или косвенной. Это…

Программирование на C++: от анализа проблем к разработке программ 8-е издание

ISBN: 9781337102087

Автор: Д. С. Малик

Издатель: Cengage Learning

9000 6 1 Обзор компьютеров и языков программирования2 Основные элементы C++ 3 Ввод/вывод4 Структуры управления I (выбор)5 Структуры управления Ii (повторение)6 Пользовательские функции7 Пользовательские простые типы данных, пространства имен и строковые типы8 Массивы и строки9Записи (структура)10 Классы и абстракция данных11 Наследование и композиция12 Точки, классы, виртуальные функции и абстрактные классы13 Перегрузка и шаблоны14 Обработка исключений15 Рекурсия16 Поиск, сортировка и векторный тип17 Связанные списки18 Стеки и очереди

Вопросы к главам