Лабораторная работа №4. Рекурсия. Рекурсивные алгоритмы Рекурсия. Рекурсивные алгоритмы

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

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

Рассмотрим вычисление факториала.

N! = N*(N-1)*(N-2)*….*2*1

Факториал можно вычислить рекурсивно, поскольку, факториал числа N можно легко получить из факториала числа N-1.

N! = N * (N-1)!

Алгоритм вычисления факториала можно записать так:

Факториал(N) = N * Факториал(N-1)

Это фрагмент рекурсивного обращения функции к самой себе.

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

Функция ФАКТОРИАЛ(N)

Если N>0 Тогда

Возврат N*ФАКТОРИАЛ(N-1)

Иначе

Возврат 1

КонецЕсли

Рассмотрим пример использования этой функции для вычисления, например, 4!

X = ФАКТОРИАЛ(4)

Пошагово опишем процесс вычисления факториала:

X=ФАКТОРИАЛ(4)

Если 4>0 (истина)

Возврат 4*ФАКТОРИАЛ(3)

Если 3>0 (истина)

Возврат 3*ФАКТОРИАЛ(2)

Если 2>0 (истина)

Возврат 2*ФАКТОРИАЛ(1)

Если 1>0 (истина)

Возврат 1*ФАКТОРИАЛ(0)

Если 0>0 (ложь)

Возврат 1

Возврат 1*1

Возврат 2*1

Возврат 3*2*1

Возврат 4*3*2*1

X=4*3*2*1

Пример реализации рекурсивной функции «Факториал» на языке VFP:

function факториал

lparameters n

if n=0

RETURN 1

else

return n* факториал(n-1)

endif

Пример рекурсивной процедуры для вычисления факториала на языке VBA:

Function Fact (n As Long) As Long

If n = 0 Then

Fact = 1

Else

Fact = Fact (n - 1) * n

End If

End Function

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

Всякий рекурсивный алгоритм должен состоять из двух фрагментов: в первом фрагменте должен содержаться рекурсивный вызов этой же самой процедуры с измененным значением критерия останова (в нашем случае критерий останова–длина отрезка [a,b]), а во втором фрагменте производится останов алгоритма в случае, когда критерий останова достигает критического значения (в данном случае критическое значение критерия останова–точность e, с которой определяется корень, т.е. |a-b|<e).

PUBLIC i

clear

i=0

x=0

a=3

b=10

fa=f(a)

fb=f(b)

r= корень(@a,@b,@fa,@fb,0.001)

?"Корень найден: x=", r

function корень

lparameters a,b,fa,fb,eps

LOCAL x, fx

DO case

CASE fa*fb>0

RETURN .f.

case fa=0

RETURN a

case fb=0

RETURN b

OTHERWISE

if ABS(a-b)<eps

RETURN (b+a)/2

ELSE

x=(b+a)/2

fx=f(x)

i=i+1

? " i=", i, "x=" ,x, "fx=", fx

IF fx*fa<=0

fb=fx

b=x

ELSE

fa=fx

a=x

ENDIF

RETURN корень(@a,@b,@fa,@fb,0.001)

ENDIF

ENDCASE

FUNCTION f

LPARAMETERS x

RETURN (x-8)*(x-14)