Предметный указатель

Эти процедуры содержат обращения к самим себе. Напишем в качестве примера процедуру вычисления чисел Фибоначчи

> restart;Fibonacci:=proc(n::nonnegint)
if n<2 then
RETURN(n);
fi;
Fibonacci(n-1)+Fibonacci(n-2);
end;

В этой процедуре явно определен тип переменной n - nonnegint (неотрицательное целое число). При попытке вызвать процедуру с объектом другого типа Maple выдаст сообщение об ошибке.

В процедуре применена команда RETURN (выражение), прерывающая выполнение команды и возвращающее значение "выражения".

В данной процедуре эта команда применена для возвращения числа n при n < 2. Вычислим последовательность чисел Фибоначчи от 1 до 15:

> seq(Fibonacci(i),i=0..15);

С целью увеличения скорости выполнения расчетов в рекурсивных процедурах вводится опция remember, при помощи которой сохраняется в памяти предыдущий результат вычисления. С применением этой опции процедура вычисления чисел Фибоначчи запишется в следующем виде:

> F:=proc(n::nonnegint)
option remember;
if n<2 then
RETURN(n)
fi;
if irem(n,2)=0 then
F(n):=2*F(n/2-1)*F(n/2)+F(n/2)^2 else
F(n):=F((n-1)/2+1)^2+F((n-1)/2)^2 fi;
end;

Если в первом варианте процедуры время вычисления каждого следующего числа Фибоначчи увеличивается по экспоненте, то во втором линейно с увеличением n. Так, например, 2000 -е число Фибоначчи вычисляется почти мгновенно:

> F(2000);

В то же время для первого варианта процедуры уже 20 - е число Фибоначчи вычисляется несколько секунд. Сравним при помощи команды time времена, затрачиваемые процедурами для вычисления 20 -ого числа Фибоначчи:

> time(F(20));time(Fibonacci(20));

Предметный указатель