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