Question

Ниже записаны две рекурсивные функции, F и G: 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(7)?

Answer 1

F(7) = F(6) + G(5) = F(5) + G(4) + G(4) + F(3) = F(4) + G(3) + G(3) + F(2) + G(3) + F(2) + F(2) + G(1) = F(3) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = F(2) + G(1) + 10 = 12

Answer 2

Давайте рассмотрим, как будут вычисляться значения функций F и G при вызове F(7).

Функции F и G определены следующим образом:

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(7):

1. F(7) = F(6) + G(5) 2. F(6) = F(5) + G(4) 3. F(5) = F(4) + G(3) 4. F(4) = F(3) + G(2) 5. F(3) = F(2) + G(1) 6. F(2) = F(1) + G(0) (base case, так как n <= 2) 7. F(1) = 1 (base case) 8. G(0) = 1 (base case) 9. G(1) = G(0) + F(-1) (base case, так как n <= 2) 10. G(2) = G(1) + F(0) 11. G(3) = G(2) + F(1) 12. G(4) = G(3) + F(2) 13. G(5) = G(4) + F(3)

Теперь подставим полученные значения обратно:

1. F(7) = F(6) + G(5) 2. F(7) = (F(5) + G(4)) + G(5) 3. F(7) = ((F(4) + G(3)) + G(4)) + G(5) 4. F(7) = (((F(3) + G(2)) + G(3)) + G(4)) + G(5) 5. F(7) = ((((F(2) + G(1)) + G(2)) + G(3)) + G(4)) + G(5) 6. F(7) = ((((F(1) + G(0)) + G(1)) + G(2)) + G(3)) + G(4)) + G(5) 7. F(7) = ((((1 + 1) + G(1)) + G(2)) + G(3)) + G(4)) + G(5) 8. F(7) = ((((1 + 1) + (G(0) + F(-1))) + G(2)) + G(3)) + G(4)) + G(5) 9. F(7) = ((((1 + 1) + (1 + 1)) + G(2)) + G(3)) + G(4)) + G(5) 10. F(7) = ((((1 + 1) + (1 + 1)) + (G(1) + F(0))) + G(3)) + G(4)) + G(5) 11. F(7) = ((((1 + 1) + (1 + 1)) + (1 + 1)) + G(3)) + G(4)) + G(5) 12. F(7) = ((((1 + 1) + (1 + 1)) + (1 + 1)) + (G(2) + F(1))) + G(4)) + G(5) 13. F(7) = ((((1 + 1) + (1 + 1)) + (1 + 1)) + (1 + 1)) + G(4)) + G(5) 14. F(7) = ((((1 + 1) + (1 + 1)) + (1 + 1)) + (1 + 1)) + (G(3) + F(2))) + G(5) 15. F(7) = ((((1 + 1) + (1 + 1)) + (1 + 1)) + (1 + 1)) + (1 + 1) + G(5) 16. F(7) = ((((1 + 1) + (1 + 1)) + (1 + 1)) + (1 + 1)) + (1 + 1) + (G(4) + F(3))) 17. F(7) = ((((1 + 1) + (1 + 1)) + (1 + 1)) + (1 + 1)) + (1 + 1) + (1 + 1) + G(5) 18. F(7) = ((((1 + 1) + (1 + 1)) + (1 + 1)) + (1 + 1)) + (1 + 1) + (1 + 1) + (G(3) + F(2))) 19. F(7) = ((((1 + 1) + (1 + 1)) + (1 + 1)) + (1 + 1)) + (1 + 1) + (1 + 1) + (1 + 1) 20. F(7) = ((((1 + 1) + (1 + 1)) + (1 + 1)) + (1 + 1)) + (1 + 1) + (1 + 1) + 2

Таким образом, значение F(7) равно 20.