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