Neefektīvas rekursijas piemērs
Var gadīties, ka rekursīva funkcija ir neefektīva un lēna. Parādīsim to ar "naivās" Fibonači skaitļu aprēķināšanas funkcijas piemēru.
Fibonači skaitļiem ir šāda rekursīva definīcija:
\( F_0 = 0 \\ F_1 = 1 \\ F_n = F_{n-1} + F_{n-2} \)
Atbilstošā funkcija to aprēķināšanai ir šāda:
function fib(n: integer): integer;
begin
if n = 0 then fib := 0;
if n > 0 then fib := fib(n-1) + fib(n-2);
end;
Lūk ilustrācija tam, kā šī funkcija izsauc pati sevi.
Kā redzams, rekursijas gaitā šī funkcija var vienu un to pašu vērtību aprēķināt ļoti daudzas reizes. Tāpēc šāda funkcija Fibonači skaitļu rēķināšanai nav izdevīga.
Svarīgi!
Izmantojot rekursīvas funkcijas, ir jāpievērš uzmanība tam, vai rekursijas gaitā netiks vairākkārtīgi aprēķināta viena un tā pati vērtība.