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