Рекурсия это в программировании: Как работает рекурсия – объяснение в блок-схемах и видео / Хабр

Содержание

Рекурсивное программирование

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

От рекурсии может заболеть голова

Я думаю, что тем, кто пытается постигнуть концепцию рекурсии, следует сначала понять, что рекурсия — это больше, чем просто практика в программировании. Это философия решения проблем, которые можно решать частями, не трогая основную часть проблемы, при этом, проблема упрощается или становится меньше. Рекурсия применима не только в программировании, но и в простых повседневных задачах. Например, возьмите меня, пишущего эту статью: допустим, я хочу написать около 1000 слов, и ставлю цель писать 100 слов каждый раз, когда сажусь за работу. Получается, что в первый раз я напишу 100 слов и оставляю 900 слов на потом.

В следующий раз я напишу ещё 100 слов, а оставлю 800. Я буду продолжать, пока не останется 0 слов. Каждый раз, я частично решаю проблему, а оставшаяся часть проблемы уменьшается.

Работу над статьей можно представить в виде такого кода:

write_words(words_left):
if words left > 0:
write_100_words()
words_left = words_left - 100
write_words(words_left)

Также, этот алгоритм можно реализовать итеративно:

write_words(words_left):
while words_left > 0:
write_100_words()
words_left = words_left - 100

Если рассматривать вызов функции write_words(1000)

в любой из этих реализаций, вы обнаружите, одинаковое поведение. На самом деле, каждую задачу, которую можно решить с помощью рекурсии, мы также можем решить с помощью итерации (циклы forи while). Так почему же стоит использовать именно рекурсию?

Я пишу статью рекурсивно

Почему рекурсия?

Хотите верьте, хотите нет, но с помощью рекурсии некоторые проблемы решить легче, чем с помощью итерации. Иногда рекурсия более эффективна, иногда более читаема, а иногда просто быстрее реализуется. Некоторые структуры данных, такие как деревья ― хорошо подходят для рекурсивных алгоритмов. Существуют языки программирования, в которых вообще нет понятия цикла — это чисто функциональные языки, такие как Haskell, они полностью зависят от рекурсии для итеративного решения задач. Я хочу сказать, что программисту не обязательно понимать рекурсию, но хороший программист, просто обязан в этом разбираться. Более того, понимание рекурсии сделает вас отличным «решателем» проблем, не только в программировании!

Суть рекурсии

В общем, рекурсивный подход подразумевает разделение сложной задачи, на один простой шаг к её решению и оставшуюся часть, которая становится упрощённой версией той же задачи. Затем этот процесс повторяется. Каждый раз вы совершаете один шаг, до тех пор, пока задача упростится до одного простейшего решения (его называют «базовым случаем»). Простейшее решение нашего базового случая с шагами, которые мы предприняли, чтобы добраться до него, образуют решение нашей первоначальной задачи.

Мы каждый раз разделяем задачу «P» на шаги и оставшуюся упрощённую задачу той же формы, что и оригинал, пока не достигнем простого решения небольшой проблемы (базовый случай).

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

f для всех форм этого типа данных. Каждая из этих форм проще общей сложности dₒ, которую нам нужно определить. Следовательно, если мы можем найти способ выражения f(dₒ), исходя из одной или нескольких частей f(d), где все эти d проще, чем dₒ, значит мы нашли решение для f(dₒ). Мы повторяем этот процесс, и рассчитываем, что в какой-то момент оставшиеся f(d) станут настолько простыми, что мы сможем легко реализовать фиксированное, окончательное решение для них. В итоге, решением исходной задачи станет поэтапное решение более простых задач.

В приведённом выше примере (про написание статьи), данными является текст, содержащийся в документе, который я должен написать, а степень сложности — это длина документа.

Это немного надуманный пример, но если предположить, что я уже решил задачу f(900) (написать 900 слов), то все, что мне нужно сделать, чтобы решить f(1000), ― это написать 100 слов и выполнить решение для 900 слов, f(900).

Давайте рассмотрим пример получше: с числами Фибоначчи, где 1-е число равно 0, второе равно 1, а nᵗʰ число равно сумме двух предыдущих. Предположим, у нас есть функция Фибоначчи, которая сообщает нам nᵗʰ число:

fib(n):
if n == 0:
return 0
if n == 1:
return 1
else:
return fib(n-1) + fib(n-2)

Как будет выглядеть выполнение такой функции? Возьмём для примера

fib(4):

Визуализация древа рекурсии, показывающая рекурсивное вычисление, которое приводит к fib(4) = 3. Обратите внимание, что вычисление сначала выполняется в глубину.

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

fib(n) мы действуем, как будто мы уже рассчитали fib(n-1) и fib(n-2). В тоже время мы рассчитываем, что эти каскады и упрощения приведут к более простым случаям, пока мы не достигнем fib(0) и fib(1), которые имеют фиксированные и простые решения.

«Притворяйся, пока это не станет правдой»

Рекурсивная стратегия

Рекурсивный подход — дело тонкое, и зависит от того, какую проблему вы пытаетесь решить. Тем не менее, есть некоторая общая стратегия, которая поможет вам двигаться в правильном направлении. Эта стратегия состоит из трёх шагов:

Упорядочить данные
Решить малую часть проблемы
Решить большую часть проблемы

Как я уже говорил, я думаю, что для обучения полезно приводить пример, но помните, что рекурсивный подход зависит от конкретной задачи. Поэтому старайтесь сосредоточиться на общих принципах. Мы рассмотрим простой пример с реверсом строки. Мы напишем функцию reverse,которая будет работать так: reverse('Hello world') = 'dlrow olleH'

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

Упорядочивание данных

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

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

По порядку рассчитайсь, йехуу!

После того, как мы упорядочили данные, нам нужно подумать об этом, как о чём-то, что мы можем сократить. На самом деле, мы можем записать наш порядок в виде последовательности:

0, 1, 2, …, n для чисел (т.е. для int данных d, степень(d) = d)

[], [■], [■, ■], …, [■, … , ■] для списков (len = 0, len = 1, …, len = n и т.д. для списка d, степень(d) = len(d))

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

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

Решаем малую часть проблемы

Как правило это самая лёгкая часть. После того, как мы определились с порядком, мы должны выделить в нём самые маленькие элементы, и решить, как мы будем обрабатывать их. Обычно, можно найти очевидное решение: в случае reverse(s), как только мы дойдём до len(s) == 0, имея при этом reverse('')

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

Переходим к общим случаям

На этом этапе мы обрабатываем данные двигаясь вправо, то есть в сторону высокой степени. Как правило, мы рассматриваем данные произвольной степени, и ищем способ решения проблемы, упрощая её до выражения, представляющего ту же проблему, но в меньшей степени. Например, в случае с числами Фибоначчи мы начали с произвольного значения n и упростили fib(n) до fib(n-1) + fib(n-2), что является выражением, содержащим два экземпляра той же задачи, но в меньшей степени (n-1 и n-2, соответственно).

Большой случай?

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

reverse(string) = reverse(string[-1]) + reverse(string[:-1])

где string[-1] соответствует последнему символу, а string[:-1]соответствует строке без последнего символа (это питонизм). Последний член функции reverse(string[:-1]), и является нашей исходной задачей, но он оперирует со строкой длины n-1. Таким образом, мы выразили нашу исходную задачу в решении той же задачи, но в уменьшенной степени.

Применив это решение к функции reverse, мы получаем следующее:

reverse(string):
  if len(string) == 0:
    return ''
  else:
    return string[-1] + reverse(string[:-1])

Визуализации рекурсивной функции reverse

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

Напутствие

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

Иногда в более сложных рекурсивных задачах, шаги 2 и 3, о которых мы говорили, принимают форму более циклического процесса. Если вы не можете быстро найти общее решение проблемы, попробуйте решить рекурсивные (большие) случаи и базовые (маленькие) случаи, которые сможете найти, а затем посмотрите, как в результате разделились разные части данных. Это должно выявить любые недостающие базовые и рекурсивные случаи или те, которые плохо взаимодействуют друг с другом и нуждаются в переосмыслении.

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

На этом всё, спасибо за внимание.

Перевод статьи Tom Grigg: Recursive Programming

Рекурсия — это… Что такое Рекурсия?

Рекурсивное изображение экрана Визуальная форма рекурсии страницы Википедии

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

Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике. В математике и информатике рекурсия имеет отношение к методу определения функций: рекурсивно заданная функция в своём определении содержит себя, в частности, рекурсивной является функция, заданная рекуррентной формулой. Таким образом, можно одним выражением дать бесконечный набор способов вычисления функции, определить множество объектов через самого себя с использованием ранее заданных частных определений.

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

В математике

В программировании

Функции

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

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

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

Имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивается выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. Однако, далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Scheme (диалект языка Lisp), описание которого содержит все необходимые сведения.

Любую рекурсивную функцию можно заменить циклом и стеком.

Данные

Описание типа данных может содержать ссылку на саму себя. Подобные структуры используются при описании списков и графов. Пример описания списка (C++):

 struct element_of_list
 {
   element_of_list *next; /* ссылка на следующий элемент того же типа */
   int data; /* некие данные */
 };

Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных.

В физике

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

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

В лингвистике

См. также: Рекурсия (лингвистика)

Способность языка порождать вложенные предложения и конструкции. Базовое предложение «кошка съела мышь» может быть за счёт рекурсии расширено как Ваня догадался, что кошка съела мышь, далее как Катя знает, что Ваня догадался, что кошка съела мышь и так далее. Рекурсия считается одной из лингвистических универсалий, то есть свойственна любому естественному языку. Однако, в последнее время активно обсуждается возможное отсутствие рекурсии в одном из языков Амазонии — пираха, которое отмечает лингвист Дэниэл Эверетт (англ.)^[1].

В культуре

Большая часть шуток о рекурсии касается бесконечной рекурсии, в которой нет условия выхода, например, известно высказывание: «чтобы понять рекурсию, нужно сначала понять рекурсию».

Весьма популярна шутка о рекурсии, напоминающая словарную статью:

Несколько рассказов Станислава Лема посвящены (возможным) казусам при бесконечной рекурсии:

рассказ про Йона Тихого «Путешествие четырнадцатое» из «Звёздных дневников Ийона Тихого», в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки»:

Нашёл следующие краткие сведения:
«СЕПУЛЬКИ — важный элемент цивилизации ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКАРИИ».
Я последовал этому совету и прочёл:
«СЕПУЛЬКАРИИ — устройства для сепуления (см.)».
Я поискал «Сепуление»; там значилось:
«СЕПУЛЕНИЕ — занятие ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКИ».
Лем С. «Звёздные дневники Ийона Тихого. Путешествие четырнадцатое.»

Рассказ из «Кибериады» о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей).
Рекурсивные акронимы: GNU (GNU Not Unix), PHP (PHP: Hypertext Preprocessor) и т. д.

См. также

Примечания

Что такое рекурсия и как ее использовать?

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

Что такое рекурсивная функция?

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

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

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

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

Все рекурсивные функции имеют одинаковую базовую структуру:

 FUNCTION name
IF condition THEN
RETURN result
ELSE
CALL FUNCTION name
END FUNCTION

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

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

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

Связанный: Что такое функция в программировании?

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

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

Факториалы возвращают произведение числа и всех целых чисел перед ним. Например, факториал 5 равен 5 x 4 x 3 x 2 x 1 или 120.

 def factorialFunction(numberToMultiply):
if numberToMultiply == 1 :
return 1
else :
return numberToMultiply * factorialFunction(numberToMultiply - 1)result = factorialFunction(3)
print(result)
//Outputs: 6

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

Когда функция вызывается, numberToMultiply равно 3.
Условие не выполняется, поэтому переходим к условию else .
Наша функция возвращает 3 *, но затем останавливается. Он должен вызвать себя, чтобы определить остальную часть возвращаемого значения.
Когда на этот раз вызывается функция, значение numberToMultiply равно 2.
Условие не выполняется, поэтому переходим к условию else.
Наша функция возвращает 2 *, но затем останавливается. Он должен вызвать себя, чтобы определить остальную часть возвращаемого значения.
Функция вызывается снова. На этот раз значение numberToMultiply равно 1.
Наше условие if выполнено. Функция возвращает 1.
Функция из шага 6 теперь может возвращать 2 * 1 функции из шага 3.
Функция на третьем шаге теперь может возвращать 3 * 2 * 1, что равно 6.

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

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

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

Пример преобразования цикла в рекурсивную функцию

 print("Enter an even number:")
i = int(input())
while (i % 2) != 0 :
print("That number is not even. Please enter a new number:")
i = int(input())

Этот цикл также можно записать рекурсивно как:

 def recursiveFunction(number) :
if (number % 2) == 0 :
return number
else:
print("That number is not even. Please enter a new number:")
recursiveFunction(int(input()))print("Enter and even number:")
i = recursiveFunction(int(input()))

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

Чтобы настроить цикл, мы снова вызываем нашу функцию. Но на этот раз число, которое мы передаем следующей функции, – это новый номер, введенный пользователем. Следующий вызов функции проверит номер.

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

Связанный: Основные примеры Python, которые помогут вам быстро изучить

Реальный пример рекурсивной функции

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

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

Представьте, что мы ищем число шесть на дереве выше. Мы могли бы создать рекурсивную функцию, которая просматривает дерево слева направо. Алгоритм выглядел бы примерно так:

 FUNCTION searchTree(branchToSearch)
IF find 6 OR end of tree THEN
RETURN result
ELSE
PROCESS branch
CALL FUNCTION searchTree(left)
CALL FUNCTION searchTree(right)
END FUNCTION

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

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

Если бы алгоритмы просматривали все дерево, они бы делали это в следующем порядке:

2, 7, 2, 6, 5, 11, 5, 9 и 4

Посмотрите, сможете ли вы продолжить, используя приведенный выше псевдокод.

Обзор рекурсии

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

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

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

Связанный

Как работает Рекурсия в Python — пример рекурсивной функции

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

Рекурсивную функцию поиска факториала.
Как рекурсивные функции работают в коде.
Действительно ли рекурсивные функции выполняют свои задачи лучше итеративных?

Рекурсивные функции

Рекурсивная функция — это та, которая вызывает сама себя.

В качестве простейшего примера рассмотрите следующий код:


def factorial_recursive(n):
if n == 1:
return n
else:
return n*factorial_recursive(n-1)

Вызывая рекурсивную функцию здесь и передавая ей целое число, вы получаете факториал этого числа (n!).

Вкратце о факториалах

Факториал числа — это число, умноженное на каждое предыдущее число вплоть до 1.

Например, факториал числа 7:
7! = 7*6*5*4*3*2*1 = 5040

Вывести факториал числа можно с помощью функции:


num = 3
print(f"Факториал {num} это {factorial_recursive(num)}")

Эта функция выведет: «Факториал 3 это 6». Еще раз рассмотрим эту рекурсивную функцию:

def factorial_recursive(n):

    ...

По аналогии с обычной функцией имя рекурсивной указывается после def, а в скобках обозначается параметр n:

def factorial_recursive(n):
    if n == 1:
        return n
    else:
        return n*factorial_recursive(n-1)

Благодаря условной конструкции переменная n вернется только в том случае, если ее значение будет равно 1. Это еще называют условием завершения. Рекурсия останавливается в момент удовлетворения условиям.

def factorial_recursive(n):
    if n == 1:
        return n
    else:
        return n*factorial_recursive(n-1)

В коде выше выделен фрагмент самой рекурсии. В блоке else условной конструкции возвращается произведение n и значения этой же функции с параметром n-1.

Это и есть рекурсия. В нашем примере это так сработало:

3 * (3-1) * ((3-1)-1)  # так как 3-1-1 равно 1, рекурсия остановилась

Детали работы рекурсивной функции

Чтобы еще лучше понять, как это работает, разобьем на этапы процесс выполнения функции с параметром 3.

Для этого ниже представим каждый экземпляр с реальными числами. Это поможет «отследить», что происходит при вызове одной функции со значением 3 в качестве аргумента:


# Первый вызов
factorial_recursive(3):
if 3 == 1:
return 3
else:
return 3*factorial_recursive(3-1)# Второй вызов
factorial_recursive(2):
if 2 == 1:
return 2
else:
return 2*factorial_recursive(2-1)
# Третий вызов
factorial_recursive(1):
if 1 == 1:
return 1
else:
return 1*factorial_recursive(1-1)

Рекурсивная функция не знает ответа для выражения 3*factorial_recursive(3–1), поэтому она добавляет в стек еще один вызов.

Как работает рекурсия

/\ factorial_recursive(1) - последний вызов
|| factorial_recursive(2) - второй вызов
|| factorial_recursive(3) - первый вызов

Выше показывается, как генерируется стек. Это происходит благодаря процессу LIFO (last in, first out, «последним пришел — первым ушел»). Как вы помните, первые вызовы функции не знают ответа, поэтому они добавляются в стек.

Но как только в стек добавляется вызов factorial_recursive(1), для которого ответ имеется, стек начинает «разворачиваться» в обратном порядке, выполняя все вычисления с реальными значениями. В процессе каждый из слоев выпадает в процессе.

factorial_recursive(1) завершается, отправляет 1 в
factorial_recursive(2) и выпадает из стека.
factorial_recursive(2) завершается, отправляет 2*1 в
factorial_recursive(3) и выпадает из стека. Наконец, инструкция else здесь завершается, возвращается 3 * 2 = 6, и из стека выпадает последний слой.

Рекурсия в Python имеет ограничение в 3000 слоев.


>>> import sys
>>> sys.getrecursionlimit()
3000

Рекурсивно или итеративно?

Каковы же преимущества рекурсивных функций? Можно ли с помощью итеративных получить тот же результат? Когда лучше использовать одни, а когда — другие?

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

Рекурсия может быть медленной, если реализована неправильно

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

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


def factorial_iterative(num):
factorial = 1
if num < 0:
print("Факториал не вычисляется для отрицательных чисел")
else:
for i in range (1, num + 1):
factorial = factorial*i
print(f"Факториал {num} это {factorial}")

О пользе рекурсии

Эту заметку о пользе рекурсии я написал после прочтения соответствующей части книги С. Макконнелла «Совершенный код». Книга прекрасная, но, на мой взгляд, автор совершенно напрасно обещает уволить сотрудника, использующего рекурсию. Мне рекурсия помогала много раз, и я видел множество превосходных примеров её использования.

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

Компактность записи

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

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

# пример 1
# вычисление факториала на языке Python без рекурсии
def fac(n):
    f = 1
    i = 2
    while i <= n:
        f *= i
        i += 1
    return f

Многие могут сказать, что функция чрезмерно усложнена добавлением переменной i. Чуть ниже, я поясню, зачем я это сделал, а пока приведу классический вариант:

# пример 2
# Python; без рекурсии; классика
def fac(n):
    f = 1
    while n > 1:
        f *= n
        n -= 1
    return f

У такого подхода есть один важный недостаток, к нему мы скоро вернёмся. А пока давайте посмотрим на рекурсивные реализации.

Сперва классическая реализация с рекурсией, всё на том же Python:

# пример 3
# Python; с рекурсией; классика
def fac(n):
    if n == 0:
        return 1
    else:
        return n * fac(n-1)

Обратите внимание, на сколько близко эта запись перекликается с математическим определение факториала.

Можно сэкономить одну строчку:

# пример 4 (экономичная запись примера 3)
# Python; с рекурсией; классика
def fac(n):
    if n == 0:
         return 1
    return n * fac(n-1)

Ту же самую мысль можно записать ещё компактней

# пример 5 (одно-строчная запись примера 3)
def fac(n): return (1 if n == 0 else n * fac(n-1))

Этот пример работает только в Python 2.5 и старше.

Приведу два примера на Haskell:

-- пример 7
-- запись примера 3 на Haskell
fac n = if n == 0
          then 1
          else n * fac (n-1)

Приведу ещё один, более компактный, но вполне понятный для неподготовленного читателя:

-- пример 8
-- реализация рекурсивного вычисления факториала
-- на Haskell; дополнительно компактности удалось
-- достичь за счёт использования клозов (от clause)
fac 0 = 1
fac n = n * fac (n-1)

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

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

Как же можно повысить понятность кода, используя рекурсию?

Неизменяемость переменных

При программировании бывает полезно придерживаться концепции неизменяемости переменных (многие языки программирования вообще не допускают изменения переменных). Это позволяет убить сразу много зайцев:

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

Давайте рассмотрим эти аспекты подробней.

Избавление от сайд-эффектов (side effect)

Рассмотрим рекурсивную и не рекурсивную реализацию. Повторю их здесь.

Не рекурсивная (одна из, она мне нравится больше; почему — поясню ниже)

# пример 1
# вычисление факториала на языке Python без рекурсии
def fac(n):
    f = 1
    i = 2
    while i <= n:
        f *= i
        i += 1
    return f

Тут мы видим сразу две изменяемые переменные — f и i. Причём i оказывает влияние на f в одном месте, а изменяет своё значение — в другом. Это потенциальный источник ошибок такого вида:

# пример 1 с ошибкой
def fac(n):
    f = 1
    i = 2
    while i <= n:
        i += 1 # Ошибка
        f *= i # Порядок выполнения операций не верный
    return f

Даже в таком тривиальном коде заметить ошибку не легко. С увеличением объёма кода, находить ошибки, связанные с побочными эффектам, становится очень сложно.

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

Вариант с рекурсией полностью избавлен от этого недостатка (приведу его здесь снова):

# пример 3
# Python; с рекурсией; классика
def fac(n):
    if n == 0:
        return 1
    else:
        return n * fac(n-1)

В процессе выполнения функции fac ни одна переменная не изменяется. Это обстоятельство может сильно упростить чтение и понимание кода.

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

Лёгкость проверки корректности значений

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

Строго говоря, проверка становится вполне естественной веткой в существующем алгоритме. Вот модифицированный пример 3:

# пример 3 с проверкой значений на "не-отрицательность"
def fac(n):
    if n == 0:
        return 1
    if n >  0:
        return n * fac(n-1)
    else:
        return 'ERROR'

Чтобы реализовать аналогичную проверку в не рекурсивном варианте кода (примеры 1 и 2), пришлось бы добавить отдельный проверяющий механизм. И это не случайно, причины кроются в различном подходе к работе с данными. К этим различиям я ещё вернусь в секции «»Данные, управляемые программами» против «программ, управляемых данными»».

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

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

Взгляните ещё раз на рекурсивный пример 3: переменная n сохраняет единственное назначение.

Чтобы идея была понятней, давайте введём ещё одну переменную (конечно же, она тоже будет неизменяемой):

# пример 3 с дополнительно переменной
def fac(n):
    if n == 0:
        f = 1
    else:
        f = n * fac(n-1)
    return f

Теперь переменных две и их смысл одинаков везде, где они используются: n — аргумент, f — факториал n (и ни что иное).

Теперь пришло время объяснить, почему мне так не симпатичен пример 2 (приведу его здесь снова):

# пример 2
# Python; без рекурсии; классика
def fac(n):
    f = 1        # первое использование f
    while n > 1:
        f *= n   # второе использование f
        n -= 1
    return f     # третье использование f

Здесь переменная f используется трижды, и все три раза она имеет разный смысл:

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

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

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

И снова, источник всех бед только то, что переменная f — изменяемая.

«Данные, управляемые программами» против «программ, управляемых данными»

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

Первый — «программа управляет данными». Это наиболее простой и общеизвестный способ взаимодействия с данными. Если данные просты, то он позволяет без труда обрабатывать их, но если данные сложны (например, это некие конструкции, допускающие многократные вложения: HTML, XML, PostScript или просто программа на некотором языке высокого уровня), то алгоритму приходится обрабатывать множество возможных вариантов. Одна из наибольших проблем — обработка ошибок. Чтобы точно диагностировать ошибку, приходится рассматривать множество вариантов во множестве мест кода. Группировка проверок может значительно помочь программисту, но такой подход таит потенциальную опасность того, что значение изменится где-то между проверкой его корректности и его использованием.

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

Второй подход — «данные управляют программой». Этот подход используется в функциональных языках программирования и наиболее чисто реализован (на мой взгляд) в XSLT.

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

Давайте я приведу чуть-модифицированный вариант третьего примера:

# пример 3 (чуть модифицированный)
def fac(n):
    if n == 0: return 1
    if n != 0: return n * fac(n-1)

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

если n равно нулю, то результат -- 1
если n не равно нуля, то результат -- выражение

Эти строки можно выполнять в любом порядке. Для программиста не важно в каком порядке они будут отрабатываться. Он может отладить каждую ветку отдельно, а потом объединить их, не опасаясь сайд-эффектов. То, какая именно ветка будет работать, определятся входными данными. Поэтому подход и называется «данные управляют программой».

Подход, когда данные управляют программой даёт множество преимуществ, основными из которых являются: лёгкость понимания кода и простота написания обработчиков ложных данных, независимость одних частей кода от других. Но главное, такой подход не позволяет программисту создавать «дырки».

Рекурсия расточительна

«More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason — including blind stupidity.»
— W. A. Wulf
«We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.»
— C. A. R. Hoare

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

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

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

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

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

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

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

def fac(n, a=None):
    if a is None:
        a = 1
    if n < 2:
        return a
    return fac(n - 1, a * n)

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

Она характерна тем, что после рекурсивного вызова не выполняется никаких действий (наш предыдущий вариант таким свойством не обладал). В этом случае компилятор может превратить рекурсию в цикл. В gcc это сделает уже -O2-оптимизация. То есть, мы получили рекурсию без дополнительных накладных расходов.

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

Рекурсия позволяет создавать код с неизменяемыми переменными, что

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

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

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

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

В любом случае, существует множество языков, в которых рекурсия — единственное средство, для выполнения многих действий. К таким языкам относятся не только «экзотические» функциональные языки, такие как Haskell, но и средства более широкого применения: XSLT-процессоры, макро-процессор m4 (основа системы autoconf и многих систем конфигурирования), и другие средства. Такое «тяготение» к рекурсии — не следствие ограниченности этих языков; напротив, эти языки специально оптимизированы для использования рекурсии; они активно эксплуатируют факт неизменяемости переменных и способны выполнить множество оптимизаций, избавляя программиста от многих забот.

Отправить

Когда использовать рекурсию?

От того, кто практически живет в рекурсии, я постараюсь пролить свет на эту тему.

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

Если вы узнаете больше о функциональном программировании, таком как F #, вы узнаете, что списки F # реализованы в виде односвязных списков, что означает, что операции, которые обращаются только к заголовку списка, являются O (1), а доступ к элементу — O (n). Когда вы узнаете это, вы стремитесь просмотреть данные в виде списка, создавая новый список в обратном порядке, а затем переворачивая список, прежде чем вернуться из функции, которая очень эффективна.

Теперь, если вы начнете думать об этом, вы скоро поймете, что рекурсивные функции будут выдвигать кадр стека каждый раз, когда выполняется вызов функции, и могут вызвать переполнение стека. Однако, если вы создаете свою рекурсивную функцию, чтобы она могла выполнять хвостовой вызов, а компилятор поддерживает возможность оптимизировать код для хвостового вызова. т.е. .NET OpCodes.Tailcall Field вы не будете вызывать переполнение стека. С этого момента вы начинаете писать любой цикл как рекурсивную функцию, а любое решение — как совпадение; дни ifи whileтеперь история.

Как только вы переходите на ИИ, используя возврат на таких языках, как PROLOG, все становится рекурсивным. Хотя для этого нужно думать совершенно иначе, чем просто для императивного кода, если PROLOG является подходящим инструментом для решения проблемы, он освобождает вас от необходимости писать много строк кода и может значительно сократить количество ошибок. Смотрите: Amzi клиент eoTek

Вернемся к вашему вопросу о том, когда использовать рекурсию; Я смотрю на программирование одним способом: на одном конце — аппаратное обеспечение, а на другом — абстрактные концепции. Чем ближе к проблеме аппаратного обеспечения, тем больше я думаю о императивных языках ifи whileчем более абстрактно эта проблема, тем больше я думаю о языках высокого уровня с рекурсией. Однако, если вы начнете писать системный код низкого уровня и тому подобное и хотите убедиться, что он действителен, вам пригодятся такие решения, как средства доказательства теорем , которые в значительной степени зависят от рекурсии.

Если вы посмотрите на улицу Джейн, вы увидите, что они используют функциональный язык OCaml . Хотя я не видел ни одного из их кода, прочитав о том, что они упоминают о своем коде, они угрюмо думают рекурсивно.

РЕДАКТИРОВАТЬ

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

Для C ++: если вы определяете структуру или класс, который имеет указатель на ту же структуру или класс, тогда рекурсия должна быть рассмотрена для методов обхода, которые используют указатели.

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

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

Обычное использование рекурсии:

определение. Рекурсия в программировании (примеры)

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

Слово «рекурсия» имеет целый спектр значений, которые зависят от области, в которой оно применяется. Универсальное обозначение является таким: рекурсии — это определения, изображения, описания объектов или процессов в самих объектах. Возможны они только в тех случаях, когда объект является частью самого себя. По-своему определяют рекурсию математика, физика, программирование и ряд других научных дисциплин. Практическое применение она нашла в работе информационных систем и физических экспериментах.

Что подразумевают под рекурсией в программировании?

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

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

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

Если читающий эти строки изучал программные циклы, то он, наверное, уже заметил схожесть между ними и рекурсией. В целом они действительно могут выполнять похожие или идентичные задания. С помощью рекурсии удобно делать имитацию работы цикла. Особенно это полезно там, где сами циклы использовать не очень удобно. Схема программной реализации не сильно различается у разных высокоуровневых языков программирования. Но всё же рекурсия в «Паскале» и рекурсия в С или другом языке имеет свои особенности. Может она быть успешно реализована и в низкоуровневых языках вроде «Ассемблера», но это является более проблематичным и затратным по времени.

Деревья рекурсии

Что такое «дерево» в программировании? Это конечное множество, состоящее как минимум из одного узла, который:

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

Другими словами: деревья содержат поддеревья, которые содержат ещё деревья, но в меньшем количестве, чем предыдущее дерево. Так продолжается до тех пор, пока в одном из узлов не останется возможности продвигаться далее, и это будет обозначать конец рекурсии. Есть ещё один нюанс насчет схематического изображения: обычные деревья растут снизу вверх, а в программировании они рисуются наоборот. Узлы, не имеющие продолжения, называются конечными узлами. Для удобства обозначения и для удобства используется генеалогическая терминология (предки, дети).

Зачем она применяется в программировании?

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

Отличия рекурсии в различных языках программирования

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

Рекурсия – это легко. Как просто запомнить содержание статьи?

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

продвинутых концепций рекурсии, которые должен знать каждый эффективный программист | by Andre Ye

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

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

Например, давайте рассмотрим задачу печати обратной стороны строки. Результатом ввода «hello» должно быть «olleh». Итерационный метод решения этой задачи заключается в использовании цикла for и распечатке каждого символа от последнего индекса до первого.

Рекурсивный метод будет первым, чтобы создать функцию reverseString , которая принимает строку в качестве параметра. Если длина ввода не равна 0 — это будет базовый или завершающий регистр — мы печатаем последнюю букву и инициируем другой экземпляр reverseString в текущей строке, исключая последний последний (поскольку он был только что напечатан) .

Обратите внимание: поскольку функция вызывается внутри себя, она сама создает цикл for. Кроме того, наличие оператора if перед вызовом другого экземпляра функции обязательно — в противном случае будет выдано RecursionError или RuntimeError , потому что сценарий не видит конца бесконечному циклу. Это похоже на бесконечный цикл , в то время как True .

Давайте посмотрим, как эта рекурсивная функция действует на «hello»:

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

Рассмотрим, например, треугольник Паскаля, в котором каждое число представляет собой сумму двух вышележащих чисел с единицами по сторонам треугольника. Как можно использовать рекурсию, чтобы найти значение любого значения в точке ( i, j )? Что такое рекуррентное отношение и базовый / завершающий случай?

Повторяющееся соотношение может быть выражено следующим уравнением:

Это очевидно, если взглянуть на график треугольника.Что еще лучше в этой формуле, так это то, что если мы продолжим использовать ее для разбиения любого местоположения ( i, j ) как суммы двух других местоположений, это неизбежно приведет к базовому случаю — 1. Треугольник Паскаля начинается с единиц, а из суммы единиц вырисовывается целая сложная картина.

Как это реализовать?

Для начала давайте найдем набор правил, чтобы определить, когда соблюден базовый вариант — значение ячейки равно 1. Обратите внимание, что единицы появляются при двух условиях: либо они находятся в первом столбце ( j = 0), либо они расположены по диагонали ( i = j ).

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

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

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

(4, 2) разбивается на (3, 1) и (3, 2), которые являются двумя числами над ним, в соответствии с нашим рекуррентным соотношением. Обратите внимание, что алгоритм на самом деле не знает, что значения этих ячеек равны 3, он просто отмечает их расположение. Мы не знаем и не заботимся о какой-либо ценности, если она не удовлетворяет нашим базовым условиям. Из наших базовых случаев (1) мы можем вычислить другие небазовые местоположения, но сначала должны быть найдены все базовые случаи.

Объяснение рекурсии — Как рекурсия работает в программировании?

Рекурсия означает «решение проблемы посредством решения меньшей версии той же проблемы» или «определение проблемы в терминах самой себя». Это широко используемая идея в программировании для решения сложных проблем путем разбиения их на более простые. В этом блоге мы рассмотрим основы рекурсии и поможем вам развить важные навыки программирования.

Рекурсия часто встречается в математике, где есть много примеров выражений, написанных в терминах самих себя.Вычисление значения n-го факториала и n-го числа Фибоначчи — лучший пример этого. Но рекурсия — это такая же концепция программирования!

  n-й Факториал: n! = п * (п-1)!
Последовательность Фибоначчи: F (n) = F (n-1) + F (n-2)

Рекурсия в реальной жизни

Предположим, вы стоите в длинной очереди из людей. Сколько людей стоит прямо за вами в очереди?

Правила

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

Решение

Вы смотрите назад и видите, есть ли там человек. Если нет, то вы можете вернуть ответ «0». Если есть человек, повторите шаг 1 и дождитесь ответа от человека, стоящего позади.
Как только человек получает ответ, он добавляет 1 для человека, стоящего за ним, и отвечает человеку, который его спросил, или человеку, стоящему перед ним.
```
  int peopleCount (Человек curr)
{
  если (noOneBehind (currPerson))
  {
      возврат 0
  }
  еще
  {
      Человек personBehind = curr.getBehind ()
      вернуть peopleCount (personBehind) + 1
  }
}
  
```

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

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

  функция void ()
{
    базовый вариант
    .. .. ...
    function () // рекурсивный вызов
    .. .. ...
}

int main ()
{
    ... .. ...
    функция ()
    ... .. ...
}

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

Рекурсивный алгоритм состоит из двух частей:

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

Стратегия рекурсивного решения проблем

Действия, которые необходимо выполнить

Определите базовый случай: подумайте о наименьшей версии проблемы и запишите решение.
Define Recursive Structure: Теперь предположим, что у нас есть функция для решения проблемы с заданным размером входных данных. Как мы можем использовать его для меньшего размера ввода и использовать ответ для решения большего размера?
Объединить базовый случай и рекурсивную структуру

О чем следует помнить

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

Основные примеры рекурсивных функций

Вычислить сумму двух чисел с помощью рекурсии

  сумма (x, y)
= x, если (y == 0)
= 1 + sum (x, y-1), если (y> 0)

Вычислить произведение двух чисел с помощью рекурсии

  произведение (x, y)
= 0, если (y == 0)
= сумма (x, произведение (x, y-1), если (y> 0)

Вычислить степень двух чисел с помощью рекурсии

  мощность (x, y)
= 1, если (y == 0)
= product (x, power (x, y-1), если (y> 0)

Понимание рекурсии через поиск факториала nth

Факториал неотрицательного целого числа — это умножение всех целых чисел, меньших или равных n.Например. факториал 5 равен 1 * 2 * 3 * 4 * 5 = 120

Рекурсивная структура

Согласно математическому определению факториала числа n, мы можем написать

  н!
= n * (n-1) * (n-2) *…. * 2 * 1
= п * (п-1)!

=> n-й факториал = n * (n-1) -й факториал

Если мы вычислим значение факториала (n-1) -й , мы можем легко вычислить значение n-го факториала . Это означает, что мы можем решить проблему размера ввода n с ее меньшей подзадачей размера ввода (n-1) .Другими словами, мы можем решить эту проблему, используя идею рекурсии.

Предположим, что функция fact (n) и fact (n-1) возвращает значение факториала n-й и (n-1) -й соответственно, тогда мы можем написать следующую рекурсивную структуру.

  факт (n) = n * факт (n-1)

Базовый корпус

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

  факт (n)
= n * факт (n-1)
= п * (п-1) * факт (п-2)
... и так далее
= n * (n-1) * (n-2) * ... * 4 * 3 * 2 * факт (1)
= n * (n-1) * (n-2) * ... * 4 * 3 * 2 * 1 * факт (0)

Факториал отрицательного числа не определен, поэтому fact (0) — это наименьшая версия проблемы факториала, на которой наша рекурсия завершится. Итак, n = 0 — это базовый случай, который вернет значение 1.

Рекурсивный псевдокод n-го факториала

  int факт (int n)
{
    если (n == 0)
        возврат 1
    вернуть n * факт (n-1)
}

Как работает рекурсия в фоновом режиме?

Если мы нарисуем поток рекурсии вышеупомянутого псевдокода, можно найти этот шаблон: мы вызываем fact (0) в последнюю очередь, но сначала возвращает значение. Точно так же мы сначала вызываем fact (n), но возвращаем значение последним. Вы нашли порядка Last In First Out (LIFO) для рекурсивных вызовов и возвращаемых значений? Да, вы поняли! За сценой компилятор использует структуру данных стека для имитации рекурсии и получения правильного вывода.Мы называем этот стек: Стек вызовов !

Порядок рекурсивных вызовов: большая проблема к меньшей проблеме
факт (n) -> факт (n-1) …-> факт (i) -> …-> факт (1) -> факт (0)
Порядок возвращаемых значений: меньшая проблема — большая проблема
факт (0) -> факт (1) …-> факт (i) -> …-> факт (n-1) -> факт (n)

Как идея стека вызовов работает в рекурсии?

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

Рекурсионные визуализации для вычисления фактов (5)

Рекурсионные визуализации для вычисления фактов (3)

Источник изображения: mit.edu

Известные рекурсивные алгоритмы

Перевернуть массив

Рекурсивная структура

  реверс (A [], l, r)
- своп (A [l], A [r])
- реверс (A, l + 1, r-1)

Базовый случай: если (l> = r), то вернуть
Отношение повторяемости: T (n) = T (n-2) + c, сложность времени = O (n)

Нахождение НОД двух чисел

Нахождение n-го Фибоначчи

Ханойская башня

Двоичный поиск