Ниже на пяти языках программирования записана рекурсивная функция F.
| Бейсик | Python |
|---|---|
FUNCTION F(n) IF n > 2 THEN F = F(n-2) + F(n\2) ELSE F = n END IF END FUNCTION
| def F(n): if n > 2: return F(n-2) + F(n//2) else: return n
|
| Паскаль | Алгоритмический язык |
function F(n: integer): integer; begin if n > 2 then F := F(n-2) + F(n div 2) else F := n end; | алг цел F(цел n) нач если n > 2 то знач := F(n-2) + F(div(n,2)) иначе знач := n все кон |
| Си | |
int F(int n) { if (n > 2) return F(n-2) + F(n/2); else return n; }
| |
Чему будет равно значение, вычисленное при выполнении вызова F(9)?
Последовательно находим:
F(0) = 0
F(1) = 1
F(2) = 2
F(3) = F(1) + F(1) = 2
F(4) = F(2) + F(2) = 4
F(5) = F(3) + F(2) = 4
F(7) = F(5) +F(3) = 6
F(9) = F(7) + F(4) = 10
Ответ: 10.