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

Рекурсия

Алгоритм УлПир

Для того чтобы отсортировать массив методом Пирамиды, необходимо выполнить такую последовательность действий:

0-й шаг: Превратить исходный массив в пирамиду (с помощью просеивания).

1-й шаг: Для N-1 элементов, начиная с последнего, производить следующие действия:

• поменять местами очередной "рабочий" элемент с первым;

• просеять (новый) первый элемент, не затрагивая, однако, уже отсортированный хвост последовательности (элементы с i-го по N-й).

Реализация алгоритма УлПир

Часть программы, реализующую нулевой шаг алгоритма УлПир, мы привели в пункте "Просеивание", поэтому здесь ограничимся только реализацией основного шага 1:

for i:= N downto 2 do

begin x:= a[1];

a[1]:= a[i];

a[i]:= x;

j:= 1;

while j<=((i-1)div 2) do

begin k:= 2*j;

if (k+1<=i-1) and (a[k]<a[k+1])

then k:= k+1;

if a[k]>a[j]

then begin x:= a[j];

a[j]:= a[k];

a[k]:= x;

j:= k

end

else break

end

end;

Пирамидальная сортировка хорошо работает с большими массивами, однако на маленьких примерах (N<20) выгода от ее применения может быть не слишком очевидна. Его сложность — N*log N.

 

В математике, да и не только в ней одной, часто встречаются объекты, определяемые при помощи самих себя. Они называются рекурсивными. Например, рекурсивно определяется функция факториал: 0! =1 n! = n*(n-1)!, для любого натурального n.

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

Например:

procedure rec1(k: byte); function rec2(k: byte): byte;

begin begin

… rec1(k+1); … … x:= rec2(k+1) …

end; end;

Eсли же несколько подпрограмм вызывают друг друга, но эти вызовы "замкнуты в кольцо", то такая рекурсия называется косвенной. В случае косвенной рекурсии возникает проблема с описанием подпрограмм: по правилу языка Pascal, нельзя использовать никакой объект раньше, чем он был описан. Следовательно, невозможно написать в программе:

procedure rec_А(k: byte);

begin

… reс_В(k+1); …

end;

procedure rec_В(k: byte);

begin

… rec_А(k+1); …

end;

И здесь полезной оказывается возможность отрывать объявление подпрограммы от ее писания. Например, для косвенной рекурсии в случае двух процедур, вызывающих друг друга (rec_A -> rec_B -> rec_A), нужно такое описание:

procedure rec_А(k: byte); forward;

procedure rec_В(k: byte);

begin

… reс_А(k+1); …

end;

procedure rec_A;

begin

… rec_В(k+1); …

end;

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

Тема: Понятие рекурсии.

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

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

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

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

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

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

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

N! = 1*2*3* . . . *(N-2)*(N-1)*N
1! = 1
0! = 1

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

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

N! = (N-1)!*N

Иными словами, чтобы получить значение факториала от числа N, достаточно умножить на N значение факториала от предыдущего числа:

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

После запуска программы на экран выводится запрос "Введите число 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 всякий раз возвращает значение, равное произведению очередного числа на факториал от предыдущего числа.

Какова максимальная глубина рекурсии в Python и как ее увеличить?

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

Итак, при выполнении рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока не будет получено тривиальное решение поставленной задачи. В нашем примере решение при N=1 тривиально, т.е. ResFact=1. Затем осуществляется возврат на верхний уровень с последовательным вычислением значения функции ResFact.

Задание. Введите текст рассмотренной выше программы и запишите файл на диск под соответствующим именем, а затем откомпилируйте его. После того, как компиляция закончится успешно, задайте для просмотра в окне отладчика переменные N, F. Установите видимыми одновременно окна редактора с текстом программы и окно просмотра. Исполните программу в пошаговом режиме с заходом в функцию и пронаблюдайте за изменением значения переменной N при рекурсивных вызовах функции ResFact.

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

1. На печать выводится сказка “О попе и его собаке” определенное число раз. ("У попа была собака, он ее любил. Она съела кусок мяса — он ее убил. В землю закопал, надпись написал …)
2. Напишите рекурсивный алгоритм нахождения степени числа. ах=ах-1*а, а0=1

Вернуться назад

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

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

Реккурентность — это рекурсивное определение функции.

Ограничение глубины рекурсии

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

N!=N((N-1)!,     для N>=1 и 0! = 1.

Это напрямую соответствует нижеследующей рекурсивной программе:

function factorial( N : integer ) : integer;

begin

if N=0 then

factorial := 1

else

factorial := N * factorial(N-1);

end;

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

В математике:
Рассмотрим последовательность чисел   в которой каждое число является суммой двух предыдущих. Это числа Фибоначчи. История предполагает, что числа Фибоначчи были придуманы в Италии (XII -XIII вв.) одним из самых выдающихся математиков того времени. Он ускорил процесс развития физики, математики, техники и астрономии, а также выпустил три работы, самая известная называется «Liber Abaci».  Формальное их определение таково:

F(1) = 1?,F(2) = 1?,F(n) = F(n ? 2) + F(n ? 1)если?, n > 2.

Функция F(n) задана рекурсивно, то есть «через себя». База — значения функции F на аргументах 1 и 2, а шаг — формула

F(n) = F(n ? 2) + F(n ? 1).

Бесконечная рекурсия в жизни:
Эффект Droste — термин для изображения специфического вида рекурсивного изображения. Изображение включает уменьшенный собственный вариант самого себя. Этот более малый вариант после этого показывает даже более малый вариант себя, и так далее. Практически это продолжается пока разрешение изображения позволяет уменьшает размер. Термин был введен в честь Droste, голландского какао.
Классическим примером бесконечной рекурсии являются два поставленные друг напротив друга зеркала: в них образуются два коридора из затухающих отражений зеркал.

Используемые источники:
1. structur.h1.ru/recurs.htm
2. ru.wikibooks.org/wiki
3. botinok.co.il/node/29842

Как выходить из глубокой рекурсии, если не с помощью GOTO?

Страницы: 1234Следующая »

Страницы: 1234Следующая »

/ Форум / Флейм / Программирование

Тема в архиве.

Рекурсия vs. какой-то процесс

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

пример рекурсии: художник рисует картину, в которой он рисует картину, в которой он рисует картину…

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

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

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

В чем отличие итеративного процесса от рекурсивного?

Главная фишка в аккумуляторе или, иными словами, в запоминании.

Рекурсивный процесс постоянно говорит «я это запомню и потом посчитаю» на каждом шаге рекурсии. «Потом» наступает в самом конце.

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

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

Рекурсивный процесс — это процесс с отложенным вычислением.

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

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

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

---

Рекурсивный процесс это чувак, который все дела откладывает на вечер пятницы.

В течение недели у него мало работы, а в пятницу завал. Но ему так нравится 🙂

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