Дан рекурсивный алгоритм. Найдите сумму чисел, которые...

Задание:

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

procedure F(n: integer);
begin
 writeln(n);
 if n < 6 then begin
 F(n+2);
 F(n*3)
 end
end;
 

Найдите сумму чисел, которые будут выведены при вызове F(1).

Решение:

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

Начинаем с единицы и строим дерево до тех пор, пока выполняется условие n < 6.

Складывая все эти числа, получаем 79

Более подробное решение аналогичной задачи - здесь.

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

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

Выполняем вычисления:

S(1) = 1 + S(3) + S(3)
S(3) = 3 + S(5) + S(9) = 12 + S(5)
S(5)=5 + S(7) + S(15) = 5 + 7 + 15 = 27

Делаем обратный ход:
S(3) = 12 + 27 = 39
S(1) = 1 + 39 + 39 = 79

Ответ: 79