Дан рекурсивный алгоритм. Сколько символов "звездочка" будет...

Задание:

Дан рекурсивный алгоритм:

procedure F(n: integer);
begin
 writeln('*');
 if n > 0 then begin
 F(n-2);
 F(n div 2)
 end
end;
 

Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?

Решение:

Решение с помощью дерева:

В этом примере на экран выводятся не значения параметра n, а символ *

Подсчитав количество «звездочек», получаем 21

Решение без дерева:

Решим задачу без дерева. Пусть S(n) – это количество «звездочек»,  которые будут выведены при вызове F(n).Тогда

Нам нужно узнать S(7):

S(7)=1+S(5)+S(3)
S(5)=1+S(3)+S(2)
S(3)=1+S(1)+S(1)
S(2)=1+S(0)+S(1)=1+1+S(1)=2+S(1)
S(1)=1+S(-1)+S(0)=1+1+1=3

Делаем обратный ход:

S(2)=2+3=5
S(3)=1+3+3=7
S(5)=1+7+5=13
S(7)=1+13+7=21

Ответ: 21