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