Рекурсивные: 16 — Рекурсивные алгоритмы - Блог сумасшедшего сисадмина

Содержание

Рекурсивное название небольшой статьи о рекурсии / Хабр

Практика преподавания и изучения программирования преимущественно на базе императивных языков (включая объектно-ориентированные императивные языки) приводит к тому, что такой фундаментальный алгоритмический механизм, как рекурсия, остаётся плохо понятным многими программистами и порождает заблуждения, транслируемые в популярной культуре. Попытаемся внести в вопрос немного ясности и изложить некоторые свои мысли по этому поводу.

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

Что такое рекурсия в бытовом понимании? Это решение задачи через сведение её к самой себе в более простых условиях.

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

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

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

Определения

Формально введём некоторые определения. Вопрос далеко не нов, поэтому возьмём определения из достаточно академичных источников, таких как [Friedman1975] и [Хювёнен1990]. В математике рекурсия рассматривается в теории рекурсивных функций, являющейся одним из формализмов теории алгоритмов, поэтому определения многих терминов имеют базу в виде очень чётко заданных математических понятий.

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

Рекурсивный вызов – прямой или опосредованный вызов функцией самой себя.

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

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

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

Параллельная рекурсия – рекурсия, встречающаяся несколько раз в одной ветви кода функции.

Взаимная рекурсия – вызов двумя или более функциями друг друга.

Рекурсия по значению – рекурсивный вызов, определяющий результат функции.

Рекурсия по аргументам – рекурсивный вызов, участвующий в вычислении аргументов функции.

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

Порядок рекурсии – уровень, на котором находится вызов в рекурсии высокого порядка. Обычные используемые на практике случаи рекурсии содержат рекурсивные вызовы нулевого порядка.

Стилизованная рекурсивная функция – некий специальный вид рекурсивной функции нулевого порядка, более общий, чем простая рекурсия, и удовлетворяющий семи довольно замысловато сформулированным требованиям, описанным в статье [Friedman1975] (желающие могут прочитать их по ссылке ниже, страницы 4-5 статьи). Авторы показывают, что стилизованная рекурсивная функция всегда может быть сведена компилятором к итеративному циклу.

Далее приведены строго не определённые понятия.

Хвостовая рекурсия – простая рекурсия, рекурсивный вызов в которой находится в конце кода функции. Многие источники в интернете называют хвостовой рекурсией только такие вызовы, которые непосредственно предшествуют возврату из функции (назовём это хвостовой рекурсией I), в то время как другие интерпретируют хвостовую рекурсию более широко, понимая её как однократный рекурсивный вызов где-либо в последней линейной ветке кода (назовём это хвостовой рекурсией II), или как простую рекурсию. По любому определению, хвостовая рекурсия является частным случаем простой рекурсии.

Оптимизация хвостовой рекурсии, или оптимизация хвостового вызова – преобразование транслятором хвостового вызова функции (необязательно рекурсивного) в линейный (циклический) код. Здесь опять-таки широк диапазон интерпретаций, начиная от простой замены пары команд call/ret на jmp (которая в том числе устраняет хвостовую рекурсию I) и заканчивая более сложными оптимизациями хвостовой рекурсии II и простой рекурсии.

Применение определений

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

Напишем псевдокод на языке Лисп для наших туристов, чтобы они точно понимали, что делать, проснувшись утром голодными и не помнящими, что у них в рюкзаках:

(defun ищемТушёнку (рюкзак)
  (cond 
    ((null рюкзак) nil)
    ((тушёнка? (car рюкзак)) (car рюкзак))
    (t (ищемТушёнку (cdr рюкзак)))))

Здесь мы определили функцию ищемТушёнку от параметра-списка рюкзак. Её тело состоит из условного оператора cond, имеющего две терминальные и одну рекурсивную ветку. Рюкзак проверяется на пустоту, затем первый элемент рюкзака (car рюкзак) проверяется специальным предикатом, не тушёнка ли это, затем по третьей ветви, которая предваряется тождественно истинным к этому моменту условием

t, уходим на рекурсивный вызов с остатком списка (cdr рюкзак).

Если есть желание довести дело до компьютерного исполняемого кода, определим также наш предикат:

(defun тушёнка? (x) (eq x 'тушёнка))

Прямо в таком виде это можно ввести в GNU Common Lisp или SBCL и искать тушёнку.

(ищемТушёнку '(носки хлеб учебникЛиспа штопор
               тушёнка смартфон ноутбук
               шишка шишка кирпич носовойПлаток
               нож кредитка конфета бумажка
               зубочистка непонятныйМусор))
ТУШЁНКА

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

Эффективность рекурсии

Многие программисты считают, что рекурсия неэффективна, так как поедает место на стеке, и ей не место в продуктовом коде. Так ли это?

Безусловно, всякий инструмент нужно применять по назначению, и для перебора чисел от 1 до N, наверное, не надо использовать рекурсивный вызов. Тем не менее, так ли ужаcна рекурсия по сравнению с итерированным циклом?

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

Этого хватит буквально на миллиарды вложенных рекурсивных вызовов. Вряд ли когда-нибудь вам понадобится рекурсия такой глубины, и даже если да, то основной проблемой, скорее всего, станет процессорное время, а не стековая память. Цикл с содержательным смыслом на миллиард итераций – это дело серьёзное. Тем не менее, проблема со стеком всё-таки есть, и о ней необходимо помнить.

Однако, как следует из приводившихся выше определений, всякая стилизованная рекурсия и тем более всякая простая рекурсия приводима к виду итеративного цикла. Многие трансляторы об этом знают, в большем или меньшем объёме.

Часто использующимся в компиляторах приёмом оптимизации является оптимизация хвостовой рекурсии, или tail call (tail recursion) optimization. Многим программистам известно, что обычно трансляторы преобразуют хвостовую рекурсию I в эквивалентный цикл, поэтому такая задача, как наш поиск в рюкзаке, после оптимизации не будет занимать место на стеке по мере продвижения в глубины рюкзака.

Однако, интернет полон мнений, что способность компилятора к оптимизации хвостовой рекурсии исчерпывается заменой пары команд call/ret на команду jmp. Поэтому, якобы, даже обычная функция факториала в виде

(defun fact (n)
  (cond
    ((zerop n) 1)
    (t (* n (fact (- n 1))))))

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

В действительности, например, у [Penman2018] разобран пример компиляции соответствующего кода в C/C++ и показано, что хвостовая рекурсия II оптимизируется и заменяется на цикл современным компилятором. Попытки выполнить такую оптимизацию вручную ни к чему не приводят на уровне машинного кода и только затрудняют понимание исходного текста.

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

На практике оказывается, что компиляторы популярных для вычислений языков (Си/Си++, Фортран) как правило, обеспечивают глубокую оптимизацию хвостовой рекурсии при включённой оптимизации. Трансляторы Лиспа оптимизируют хвостовую рекурсию в разной степени. Трансляторы Джавы и Питона не оптимизирует хвостовую рекурсию по принципиальным соображениям, так как разработчики считают важным сохранять исходную трассировку вызовов.

Оптимизация некоторых рекурсивных вычислительных процессов также может может быть достигнута путём применения механизма мемоизации.

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

Кошмары высокого порядка

Рассмотрим теперь действительно не оптимизируемую автоматически рекурсивную функцию, например, крайне вычислительно ёмкую функцию Аккермана с рекурсией первого порядка, быстро уходящей на огромную глубину. Цитируется по [Хювяйнен1990]:

(defun аккерман (m n)
  (cond
    ((= m 0) (+ n 1))
    ((= n 0) (аккерман (- m 1) 1))
    (t (аккерман (- m 1) (аккерман m (- n 1))))))

Значение (аккерман 4 1) считается на компьютере автора в SBCL за 16 секунд с занятым стеком менее 4 мегабайт, то есть стек расходуется со скоростью 256 килобайт в секунду. Таким образом, 4-гигабайтного стека хватило бы на 4.5 часа вычислений рекурсивной функции, ничего по существу не делающей, кроме углубления своей рекурсии. (Для завершённости заметим, что значение (аккерман 4 2) вычислить брутфорсом через её рекурсивное определение пока не в человеческих силах, хотя имеется более быстрый альтернативный алгоритм [Grossman1988]; и полагаем совершенно невероятным, чтобы кому-либо в практических целях понадобился вычислительный процесс, описываемый рекурсией второго и более порядка).

Вывод

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

Литература

[Хювёнен1990] Э. Хювёнен, Й. Сеппянен. Мир Лиспа. М.: Мир, 1990.

[Chandra1972] A. Chandra. Efficient compilation of linear recursive programs. Stanford AI project, STAN‑CS-72–282, 1972.

[Friedman1975] D. Friedman, D. Wise. Unwinding stylized recursions into iterations // Indiana Univ. , 1975.

[Grossman1988] J. Grossman, R. Zeitman. An inherently iterative computation of Ackermann’s function // Theoretical Computer Science Vol. 57 Issues 2-3, May 1988, pp. 327-330

[Penman2018] T. Penman. Tail Call Optimisation and C / C++

Рекурсивные перечисления — testing.swiftbook

1009 views 09.10.2015 admin_ 1

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

Например, ниже объявлено перечисление, которое хранит простые арифметические выражения:

enum ArithmeticExpression {
    case number(Int)
    indirect case addition(ArithmeticExpression, ArithmeticExpression)
    indirect case multiplication(ArithmeticExpression, ArithmeticExpression)
}

Вы так же можете написать indirect прямо перед самим перечислением, что позволит обозначить то, что все члены перечисления поддерживают индиректность:

indirect enum ArithmeticExpression {
    case number(Int)
    case addition(ArithmeticExpression, ArithmeticExpression)
    case multiplication(ArithmeticExpression, ArithmeticExpression)
}

Перечисление может хранить три вида арифметических выражений: простое число, сложение двух выражений, умножение двух выражений. Члены addition и multiplication имеют два связанных значения, которые так же являются арифметическими выражениями. Эти связанные значения делают возможным вложение выражений. Например, выражение (5 + 4) * 2 имеет цифру справа от умножения и другое выражение слева от умножения. Поскольку данные вложены, перечисление использующееся для хранения данных, также должно поддерживать вложенность-это означает, что перечисление должно быть рекурсивными. Приведенный ниже код показывает как работает рекурсивное перечисление ArithmeticExpression для (5 + 4) * 2:

let five = ArithmeticExpression.number(5)
let four = ArithmeticExpression.number(4)
let sum = ArithmeticExpression.addition(five, four)
let product = ArithmeticExpression.multiplication(sum, ArithmeticExpression.number(2))

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

func evaluate(_ expression: ArithmeticExpression) -> Int {
    switch expression {
    case let .  number(value):
        return value
    case let .addition(left, right):
        return evaluate(left) + evaluate(right)
    case let .multiplication(left, right):
        return evaluate(left) * evaluate(right)
    }
}
 
print(evaluate(product))
// Выведет "18"

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

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Рекурсивная функция | математика | Британика

Развлечения и поп-культура
География и путешествия
Здоровье и медицина
Образ жизни и социальные вопросы
Литература
Философия и религия
Политика, право и правительство
Наука
Спорт и отдых
Технология
Изобразительное искусство
Всемирная история

Этот день в истории
Викторины
Подкасты
Словарь
Биографии
Резюме
Популярные вопросы
Инфографика
Демистификация
Списки
#WTFact
Товарищи
Галереи изображений
Прожектор
Форум
Один хороший факт

Развлечения и поп-культура
География и путешествия
Здоровье и медицина
Образ жизни и социальные вопросы
Литература
Философия и религия
Политика, право и правительство
Наука
Спорт и отдых
Технология
Изобразительное искусство
Всемирная история

Britannica объясняет
В этих видеороликах Britannica объясняет различные темы и отвечает на часто задаваемые вопросы.
Britannica Classics
Посмотрите эти ретро-видео из архивов Encyclopedia Britannica.
Demystified Videos
В Demystified у Britannica есть все ответы на ваши животрепещущие вопросы.
#WTFact Видео
В #WTFact Britannica делится некоторыми из самых странных фактов, которые мы можем найти.
На этот раз в истории
В этих видеороликах узнайте, что произошло в этом месяце (или любом другом месяце!) в истории.

Студенческий портал
Britannica — лучший ресурс для учащихся по ключевым школьным предметам, таким как история, государственное управление, литература и т. д.
Портал COVID-19
Хотя этот глобальный кризис в области здравоохранения продолжает развиваться, может быть полезно обратиться к прошлым пандемиям, чтобы лучше понять, как реагировать сегодня.
100 женщин
Britannica празднует столетие Девятнадцатой поправки, выделяя суфражисток и политиков, творящих историю.
Спасение Земли
Британника представляет список дел Земли на 21 век. Узнайте об основных экологических проблемах, стоящих перед нашей планетой, и о том, что с ними можно сделать!
SpaceNext50
Britannica представляет SpaceNext50. От полета на Луну до управления космосом — мы изучаем широкий спектр тем, которые питают наше любопытство к космосу!

Содержание

Введение

Краткие факты

Связанный контент

Викторины

Числа и математика

Рекурсия Python (рекурсивная функция)

В этом руководстве вы научитесь создавать рекурсивную функцию (функция, которая вызывает сама себя).

Рекурсия — это процесс определения чего-либо в терминах самого себя.

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

Рекурсивная функция Python

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

На следующем рисунке показана работа рекурсивной функции recurse .

Ниже приведен пример рекурсивной функции для нахождения факториала целого числа.

Факториал числа — это произведение всех целых чисел от 1 до этого числа. Например, факториал 6 (обозначается как 6!) равен 9.0162 1*2*3*4*5*6 = 720 .

Пример рекурсивной функции

 def factorial(x):
    """Это рекурсивная функция
    найти факториал целого числа"""
    если х == 1:
        вернуть 1
    еще:
        возврат (x * факториал (x-1))
число = 3
print("Факториал", num, "is", factorial(num))

Вывод

  Факториал 3 равен 6

В приведенном выше примере factorial() является рекурсивной функцией, поскольку она вызывает себя.

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

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

factorial(3) # 1-й вызов с 3
3 * factorial(2) # 2-й вызов с 2
3 * 2 * factorial(1) # 3-й вызов с 1
3 * 2 * 1 # возврат из 3-го вызова как число=1
3*2# возврат со 2-го звонка
6 # возврат с 1-го вызова

Давайте посмотрим на изображение, которое показывает пошаговый процесс того, что происходит:

Наша рекурсия заканчивается, когда число уменьшается до 1. Это называется базовым условием.

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

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

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

 деф рекурсор():
    рекурсор()
рекурсор()