Question

Дан рекурсивный алгоритм: procedure F(n: integer); begin
if n > 0 then begin F(n-2); F(n-1);
end;
writeln('*');
end;

Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)? (НУЖНО РЕШЕНИЕ)

Answer 1

В случае F(0) или от меньшего числа будет напечатана одна звездочка.

В случае F(1) будут вызваны F(0) и F(-1), каждая из которых напечатает по одной звездочке и сама F(1) напечатает еще одну - итого 3.

В случае F(2) будут вызваны F(1) и F(0). F(1), как мы выяснили, в результате своей работы напечатает 3 звездочки, F(0) - одну и еще одну сама F(2). Итого: 5

Таким образом, F(3) = F(2) + F(1) + 1 = 3+5+1 = 9

F(4) = F(3) + F(2) + 1 = 9 + 5 + 1 = 15

F(5) = F(4) + F(3) + 1 = 15 + 9 + 1 = 25

Ответ: 25