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

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

Итеративное – повторяющееся действие.

Пример Умножение M*N.

Компьютер умножает на 1 и складывает и только!! Предположим, что необходимо выполнить на этом компьютере умножение 6*3.

Эта задача может быть разделена на две:

1. задача 6*2;

2. прибавить 6 к результату 1 задачи.

Вторую задачу можно выполнить. Первую задачу разделим на две:

1.1. умножить 6*1;

1.2. прибавить к результату задачи 1.1.

Названные действия представим в виде:

Multiply: =M + Multiply (M, N-1) - рекурсивный шаг.

умножение M*(N-1)

сложение M с результатом предыдущей задачи

Если N=1, то Multiply : = M - конечный шаг.

Построим рекурсивную функцию.

function Multiply (M, N: integer): integer;

{Умножение выполняется с помощью оператора +.

Предусловие: M и N определены и N>0

Постусловие: возвращение M+N}

begin

if N=1 then

Multiply: = M {конечный шаг}

else Multiply: = M + Multiply (M, N-1) {рекурсивный шаг}

end;

Трассировка рекурсивной функции

Пусть в программе есть вызов Multiply (6, 3);

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

При вызове функции Multiply M=6, N имеет значения 3, 2 и 1.

Свойства рекурсивных задач и решений

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

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

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

Последовательность действий для решения задачи

1. Вникнуть в задачу.

2. Определить в задаче конечные цели.

3. Определить в задаче рекурсивные цели.

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

if достигнут конечный шаг

then

этот шаг выполняется

else

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

ПримерMultiply (5,4)

Умножить(5*4) Умножить (5*3) Умножить (5*2) Умножить (5*1)

добавить 5 добавить 5 добавить 5

к (5*3) к (5*2) к (5*1)

Рекурсивная процедура

procedure Reverse (N: integer);

{выводит строку длиной N в порядке, обратном тому, в котором эта строка вводилась.

Предусловие: N больше или равно единице.

Постусловие: выводит N символов}

var

next: char; {следующий символ}

begin

if N=1 then

begin {конечный шаг}

read (next);

write (next)

end

else

begin {рекурсия}

Read (next)

Reverse (N-1)

Write (next)

end

end;

Трассировка выполнения оператора REVERSE (3)

Значение N передается в процедуру при её вызове, так как N – её параметр.

Значение Next первоначально не определено, так как Next – локальная переменная.

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

Последовательность действий для рекурсивного вызова Reverse (3)

Действия из одной записи активации представлены с одинаковым отступом.

Вызов Reverse со значением N, равным 3.

Считывание в NEXT первой буквы a.

Вызов Reverse со значением N, равным 2.

Считывание в NEXT второй буквы b

Вызов Reverse со значением N, равным 1.

Считывание в NEXT третьей буквы c.

Вывод третьей буквы c.

Возврат из третьего вызова.

Вывод второй буквы b.

Возврат из второго вызова.

Вывод первой буква a.

Возврат из первого вызова.

Стеки для локальных переменных и параметров

Stack -груда, куча, кипа, стопка (перевод с англ.) Структура данных-сравнение со стопкой тарелок. Когда имеет место очередной вызов такой рекурсивной процедуры, значение параметра, ассоциированное с этим вызовом, помещается на верх стека значений. При этом новая ячейка памяти (для следующего значения), содержимое которой изначально не определенно, присоединяется к стеку поверх только что занесенного туда значения. Например, если имеет место обращение к значению N или nextв процедуре Reverse, то используется соответствующее значение с верха стека. Если же имеет место рекурсивный возврат, значение, находящееся в данный момент на верху стека, удаляется и следующее значение перемещается на верх стека.

Состояние стеков при вызовах процедуры Reverse

После первого вызова процедуры Reverse

Непосредственно перед вторым вызовом процедуры Reverse буква а считывается в стек next

После второго вызова Reverse

Непосредственно перед третьим вызовом процедуры Reverse буква b считывается в стек next

После третьего вызова Reverse

В ходе выполнения процедуры в стеке next считывается c и тут же печатается, так как N в этот момент имеет значение 1(конечный шаг).

При рекурсивном возврате значения на верху стека удаляются

После первого возврата

Управление возвращается оператору write, осуществляющему вывод значения b, находящегося в этот момент на верху стека next.

После второго возврата

Управление передается оператору write, при осуществляется вывод значения c, находящегося на верху стека next.

После третьего возврата:

В Паскале эти действия выполняется автоматически.