Рекурсия
При решении сложных задач программирования эти задачи разбиваются на более простые подзадачи. Каждая из подзадач, в свою очередь, может быть разбита на еще более простые подзадачи, и т.д. Если задача в ходе такого последовательного разбиения свелась (необязательно за один шаг) сама к себе самой, имеет место рекурсия.
Если задача сводится к себе, и еще раз к себе, и так далее, то количество обращений к себе должно быть конечным.
Каждое очередное сведение задачи к себе должно приближать задачу к тривиальному случаю. В тривиальном случае задача решается по алгоритму, который более не сводит задачу к себе.
Рекурсия используется во множестве стандартных алгоритмов. Далее, в курсе лекций, тема «Рекурсивные алгоритмы» будет возобновляться многократно.
Пример.
Применяя сведение задачи к себе n раз, можно «дойти» до тривиального случая – до значения 0!, а оно равно 1.
Пример 2.
Применение такого сведения задачи к себе приводит к «зацикливанию».
Числа Фибоначчи
выражаются сами через себя при
,
но выражаются явно (дают тривиальный
случай) при
и
:
,
,
,
.
,
– Golden
Ratio.
Сумма убывающей геометрической прогрессии
,
,
есть функциональный
(а именно, степенной, по степеням
переменной
)
ряд с коэффициентами 1, 1, … .
Полиномы Фибоначчи
являются коэффициентами разложения в
степенной ряд функции
,
.
Полиномы Фибоначчи выражаются «сами через себя» при , но выражаются явно (дают тривиальный случай) при и :
,
,
Связь с числами
Фибоначчи:
TEX (Дональд Кнут)
Пример рекурсивной функции
function Fib(n: integer; x: double): double;
begin
if n < 1 then
Fib := 0
else
if n = 1 then
Fib := 1
else
if n = 2 then
Fib := x
else
Fib := x*Fib(n-1, x) + Fib(n-2, x);
end;
Пример. Ханойские башни.
var
n: integer;
procedure HanoiTowers(n, x, y, z: integer);
begin
if n = 1 then
writeln(x,'->', y)
else
begin
HanoiTowers(n-1, x, z, y);
writeln(x,’–>’, y);
HanoiTowers(n-1, z, y, x);
end;
end;
begin
readln(n);
HanoiTowers(n,1,2,3);
end.