Ниже на пяти языках программирования записаны две рекурсивные функции: F и G. Чему будет равно значение, вычисленное при выполнении вызова F(8)?

Решение:

Чтобы найти значение F(8), нужно вычислить значения функций рекурсивно, начиная с базовых случаев.

Базовый случай: если n <= 2, то F(n) = 1 и G(n) = 1.

Рекурсивные случаи:

• F(n) = F(n-1) + G(n-2)
• G(n) = G(n-1) + F(n-2)

Вычисление:

1. F(1) = 1
2. G(1) = 1
3. F(2) = 1
4. G(2) = 1
5. F(3) = F(2) + G(1) = 1 + 1 = 2
6. G(3) = G(2) + F(1) = 1 + 1 = 2
7. F(4) = F(3) + G(2) = 2 + 1 = 3
8. G(4) = G(3) + F(2) = 2 + 1 = 3
9. F(5) = F(4) + G(3) = 3 + 2 = 5
10. G(5) = G(4) + F(3) = 3 + 2 = 5
11. F(6) = F(5) + G(4) = 5 + 3 = 8
12. G(6) = G(5) + F(4) = 5 + 3 = 8
13. F(7) = F(6) + G(5) = 8 + 5 = 13
14. G(7) = G(6) + F(5) = 8 + 5 = 13
15. F(8) = F(7) + G(6) = 13 + 8 = 21

Ответ: 21