Рекурсия
 |  |
 |  |
| |
| |
| |
| |
| |
| |
Тема: Понятие рекурсии.
Рекурсия (от латинского recursio — возвращение) — это такой способ организации вычислительного процесса, при котором процедура или функция в ходе выполнения составляющих ее операторов обращается сама к себе.
Для того, чтобы такое обращение не было бесконечным, в тексте подпрограммы должно быть условие, по достижению которого дальнейшего обращения не происходит. таким образом, рекурсивное обращение может включаться только в одну из ветвей подпрограммы.
В языке Паскаль нет никаких ограничений на рекурсивные вызовы подпрограмм, необходимо только понимать, что каждый очередной рекурсивный вызов приводит к образованию новой копии локальных объектов подпрограммы и все эти копии, соответствующие цепочке активизированных и не завершенных рекурсивных вызовов, существуют независимо друг от друга
Рекурсия достаточно широко применяется в программировании, что основано на рекурсивной природе многих математических алгоритмов. А также Вы должны знать, что любой рекурсивный алгоритм можно преобразовать в эквивалентный итеративный (то есть использующий циклические конструкции).
В больших и сложных программах иногда приходится заменять рекурсию на итерацию. Дело в том, что рекурсия связана с многократными вызовами процедур, а это несколько менее эффективно при выполнении по сравнению с использованием циклов. Однако рекурсивные версии программ, как правило, гораздо короче и нагляднее.
Хорошей иллюстрацией механизма рекурсии является функция для вычисления факториала натурального числа. Вспомним, что факториалом числа называется произведение всех натуральных чисел от 1 до этого числа включительно:
Сначала покажем обычную не рекурсивную функцию для вычисления факториала, которая реализует итеративный алгоритм вычисления:
| Function NonRecFact(N:integer) : LongInt; Var i : integer; <переменная цикла > Res : LongInt; <результат> Begin Res := 1; for i := 1 to N do res := Res*i; NonResFact := Res; End; |
Вторая функция использует рекурсивные обращения, что делает ее гораздо компактнее, и основана на очевидном соотношении:
Иными словами, чтобы получить значение факториала от числа N, достаточно умножить на N значение факториала от предыдущего числа:
| Function RecFact(N:integer) : LongInt; Begin if N |
Полностью программа, вычисляющая факториал числа, будет выглядеть так:
| Program Rekurs; Var N : integer; F : Longint; Function RecFact(N:integer) : LongInt; |
После запуска программы на экран выводится запрос «Введите число N > «, затем с клавиатуры считывается введенное значение и в выражении F:=RecFact(N) вызывается функция RecFact с параметром-значением N. В подпрограмме-функции проверяется условие N<=1. Если оно выполняется, то функции ResFact присваивается значение 1 и на этом выполнение подпрограммы завершается. Если условие N<=1 не соблюдается, то выполняется вычисление произведения N*ResFact(N-1).
Вычисление произведения носит рекурсивный характер, так как при этом осуществляется вызов функции ResFact(N-1), значение которой вычисляется, в свою очередь, через вызов функции ResFact, параметром которой также будет функция ResFact, и т.д., до тех пор пока значение формального параметра N не будет равно 1. Так как базовая часть описания рекурсивной функции ResFact определяет значение ResFact для N=1, равным единице, то рекурсивные вызовы функции ResFact больше не выполняются, а наоборот выполняется вычисление функции ResFact для чисел, возрастающих от 1 до N , причем функция ResFact всякий раз возвращает значение, равное произведению очередного числа на факториал от предыдущего числа. Последнее возвращение результата вычисления функции ResFact присвоит переменной F значение произведения всех чисел от 1 до N, т.е. факториал числа N.
Итак, при выполнении рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока не будет получено тривиальное решение поставленной задачи. В нашем примере решение при N=1 тривиально, т.е. ResFact=1. Затем осуществляется возврат на верхний уровень с последовательным вычислением значения функции ResFact.
Задание. Введите текст рассмотренной выше программы и запишите файл на диск под соответствующим именем, а затем откомпилируйте его. После того, как компиляция закончится успешно, задайте для просмотра в окне отладчика переменные N, F. Установите видимыми одновременно окна редактора с текстом программы и окно просмотра. Исполните программу в пошаговом режиме с заходом в функцию и пронаблюдайте за изменением значения переменной N при рекурсивных вызовах функции ResFact.
Задание. Напишите программы, демонстрирующие выполнение рекурсивного и итеративного алгоритма для задач:
- На печать выводится сказка “О попе и его собаке” определенное число раз. («У попа была собака, он ее любил. Она съела кусок мяса — он ее убил. В землю закопал, надпись написал . )
Источник
Рекурсия, рекурсивный процесс и итеративный процесс
Рекурсия vs. какой-то процесс
Давайте для начала явно отметим отличие рекурсии (в общем смысле) от процесса. Эти понятия никак не связаны. Рекурсия — просто абстрактная концепция, которую можно наблюдать в природе, которая используется в математике и в других областях. Такая же абстрактная, как, например, музыкальная гармония.
пример рекурсии: художник рисует картину, в которой он рисует картину, в которой он рисует картину.
Теперь на секунду забудем про рекурсию, и просто подумаем про компьютеры. Для выполнения задач компьютерам нужны инструкции. Когда компьютер выполняет набор инструкций — это процесс. Ваш работающий сейчас браузер — это процесс. Простой цикл, выводящий на экран десять раз число «42» — это процесс. Некоторые задачи можно решать рекурсивно, то есть в инструкциях использовать эту концепцию, когда что-то является частью самого себя. В частности, функция может быть частью самой себя, то есть вызывать саму себя.
Есть два метода решения задач с использованием рекурсии: рекурсивный процесс и итеративный процесс. Рекурсия в них не отличается: в каждом из подходов функция вызывает саму себя, рекурсивно. Отличаются способы использования идеи рекурсии.
Если продолжить аналогию с музыкальной гармонией, то можно подумать про фортепиано. При написании музыки можно использовать эту концепцию — «гармонию звуков». И можно придумать разные способы: рассчитывать частоты звуков (ноты) математическими формулами или рассчитывать правильные расстояния между клавишами. Я в детстве научился находить правильные расстояния между клавишами на фортепиано, и получал гармоничные комбинации звуков, но понятия не имел, что это за ноты. А профессиональный музыкант знает теорию и подбирает гармонию другими методами. В любом случае, гармония есть гармония, эта концепция не меняется, меняются лишь способы ее использования.
В чем отличие итеративного процесса от рекурсивного?
Главная фишка в аккумуляторе или, иными словами, в запоминании.
Рекурсивный процесс постоянно говорит «я это запомню и потом посчитаю» на каждом шаге рекурсии. «Потом» наступает в самом конце.
- Когда рекурсивный процесс считает факториал 6, то ему нужно запомнить 5 чисел, чтобы посчитать их в самом конце, когда уже никуда не деться и рекурсивно двигаться вниз больше нельзя.
- Когда мы находимся в очередном вызове функции, то где-то снаружи этого вызова в памяти хранятся эти запомненные числа.
тут прямо физически видно, как растет использование памяти: процессу нужно запоминать все больше и больше чисел
Рекурсивный процесс — это процесс с отложенным вычислением.
Итеративный процесс постоянно говорит «я сейчас посчитаю все что можно и продолжу» на каждом шаге рекурсии. Ему не нужно ничего запоминать вне вызова, он всегда считает все в первый возможный момент, и каждый шаг рекурсии может существовать в изоляции от прошлых, потому что вся информация передается из шага в шаг.
- Когда итеративный процесс считает факториал 6, то ему не нужно запоминать числа. Нужно лишь считать и передавать результат дальше, в новый вызов.
- Когда мы находимся в очередном вызове функции, снаружи этого вызова в памяти ничего не нужно запоминать.
тут видно, что использование памяти не растет
Рекурсивный процесс это чувак, который все дела откладывает на вечер пятницы. В течение недели у него мало работы, а в пятницу завал. Но ему так нравится 🙂
Итеративный процесс это чувак, который все делает при первой возможности. У него работа равномерно распределена по неделе, а пятница — просто обычный день, но последний.
Tail call optimization
Отмотаем назад и рассмотрим во взаимосвязи два утверждения относительно рекурсивных функций, использующих итеративный процесс:
- Во-первых, такие функции являются рекурсивными. Это значит, что для каждого (очередного) рекурсивного вызова в стек вызовов записывается вся информация, связанная с этим конкретным вызовом (параметры функции и её локальные переменные, адрес возврата в точку вызова). Т.е. выделяется дополнительная область памяти (лексический контекст функции, область видимости), обслуживающая данный рекурсивный вызов, а так как это стек вызовов, то контексты предыдущих рекурсивных вызовов также продолжают занимать память. Достижение большой глубины рекурсии (или же если она вовсе является бесконечной, т.е. не достигается терминальное условие выхода из рекурсии) приводит к переполнению стека (ведь он ограничен в размерах) и аварийному завершению всей программы.
- Во-вторых, в контексте каждого очередного рекурсивного вызова такой функции хранится вся необходимая информация для его успешного выполнения. Он самодостаточен и никак не зависит от предыдущих контекстов (помните, «этот чувак ничего не откладывает на потом, на вечер пятницы. «?!). В наших практиках на Хекслете мы реализовывали такое поведения благодаря использованию аккумулятора acc , передающегося в качестве аргумента из одного вызова в другой и накапливающего в себе результат вычисления необходимого значения. Получается, что, грубо говоря, на каком бы по уровню вложенности рекурсивном вызове мы не находились, все предыдущие уже не имеют значения и являются «бесполезной обузой», нагружающей память. В т.ч. это распространяется и на самый последний рекурсивный вызов (где срабатывает терминальное условие), который сразу готов вернуть готовое вычисленное значение из функции, ему не нужны для этого предыдущие контексты в стеке.
Читайте также: Язык программирования Ruby: особенности, перспективы, рынок труда
Отсюда напрашивается вопрос, как использовать рассмотренные преимущества итеративного процесса и одновременно избавиться от недостатка рекурсивных функций, т.е. от неумолимого роста использования памяти. И сразу же нарисовывается ответ — избавить процесс от заполнения стека «ненужными» контекстами предыдущих вызовов и обеспечить прямой возврат из функции при достижении терминального условия. Для этого служит так называемая Tail call optimization, или оптимизация хвостовой рекурсии (рассмотренный выше итеративный процесс как раз можно отнести к хвостовой рекурсии). Благодаря оптимизации состояния стека, она придаёт итеративному процессу вид «плоской» итерации (см. картинку выше), исключается его переполнение из-за большой глубины рекурсии.
Хвостовая рекурсия (и её оптимизация) широко используется при написании программ на функциональных языках программирования.
Источник
Занятие 1. Понятие рекурсии.
Рекурсия (от латинского recursio — возвращение) – это такой способ организации вычислительного процесса, при котором процедура или функция в ходе выполнения составляющих ее операторов обращается сама к себе.
Для того, чтобы такое обращение не было бесконечным, в тексте подпрограммы должно быть условие, по достижению которого дальнейшего обращения не происходит. таким образом, рекурсивное обращение может включаться только в одну из ветвей подпрограммы.
В языке Паскаль нет никаких ограничений на рекурсивные вызовы подпрограмм, необходимо только понимать, что каждый очередной рекурсивный вызов приводит к образованию новой копии локальных объектов подпрограммы и все эти копии, соответствующие цепочке активизированных и не завершенных рекурсивных вызовов, существуют независимо друг от друга
Рекурсия достаточно широко применяется в программировании, что основано на рекурсивной природе многих математических алгоритмов. А также Вы должны знать, что любой рекурсивный алгоритм можно преобразовать в эквивалентный итеративный (то есть использующий циклические конструкции).
В больших и сложных программах иногда приходится заменять рекурсию на итерацию. Дело в том, что рекурсия связана с многократными вызовами процедур, а это несколько менее эффективно при выполнении по сравнению с использованием циклов. Однако рекурсивные версии программ, как правило, гораздо короче и нагляднее.
Хорошей иллюстрацией механизма рекурсии является функция для вычисления факториала натурального числа. Вспомним, что факториалом числа называется произведение всех натуральных чисел от 1 до этого числа включительно:
Сначала покажем обычную не рекурсивную функцию для вычисления факториала, которая реализует итеративный алгоритм вычисления:
Function NonRecFact(N:integer) : LongInt;
for i := 1 to N do
Вторая функция использует рекурсивные обращения, что делает ее гораздо компактнее, и основана на очевидном соотношении:
Иными словами, чтобы получить значение факториала от числа N, достаточно умножить на N значение факториала от предыдущего числа:
Function RecFact(N:integer) : LongInt;
writeln(‘Для числа ‘,N,’ значение факториала равно ‘,F);
После запуска программы на экран выводится запрос «Введите число N > «, затем с клавиатуры считывается введенное значение и в выражении F:=RecFact(N) вызывается функция RecFact с параметром-значением N. В подпрограмме-функции проверяется условие N
Итак, при выполнении рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока не будет получено тривиальное решение поставленной задачи. В нашем примере решение при N=1 тривиально, т.е. ResFact=1. Затем осуществляется возврат на верхний уровень с последовательным вычислением значения функции ResFact.
Задание. Введите текст рассмотренной выше программы и запишите файл на диск под соответствующим именем, а затем откомпилируйте его. После того, как компиляция закончится успешно, задайте для просмотра в окне отладчика переменные N, F. Установите видимыми одновременно окна редактора с текстом программы и окно просмотра. Исполните программу в пошаговом режиме с заходом в функцию и пронаблюдайте за изменением значения переменной N при рекурсивных вызовах функции ResFact.
Задание. Напишите программы, демонстрирующие выполнение рекурсивного и итеративного алгоритма для задач:
1. На печать выводится сказка “О попе и его собаке” определенное число раз. («У попа была собака, он ее любил. Она съела кусок мяса – он ее убил. В землю закопал, надпись написал . )
2. Напишите рекурсивный алгоритм нахождения степени числа.
Источник
