Question

Задача 1. Ниже записаны две рекурсивные функции: Fи 6. Python def F(n): if n>2: return F(n-1) + G(n-2) else: return n def G(n): if n>2: return G(n-1) + F(n-2) else: return n+1 Чему будет равно значение, вычисленное при выполнении вызова F(6)?

Answer 1

Ответ: 17

............

Answer 2

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

def F(n):
    if n > 2:
        return F(n-1) + G(n-2)
    else:
        return n

def G(n):
    if n > 2:
        return G(n-1) + F(n-2)
    else:
        return n + 1

Посмотрим, как будут развиваться вызовы функций:

1. `F(6)`: - `F(6)` выполняет `F(5) + G(4)` - `F(5)` выполняет `F(4) + G(3)` - `F(4)` выполняет `F(3) + G(2)` - `F(3)` выполняет `F(2) + G(1)` - `F(2)` выполняет `F(1) + G(0)` - `F(1)` возвращает 1 - `G(0)` возвращает 1 - Суммируем результаты: `1 + 1 = 2` - `G(1)` выполняет `G(0) + F(-1)` - `G(0)` возвращает 1 - `F(-1)` возвращает -1 (так как n <= 2, возвращается n) - Суммируем результаты: `1 - 1 = 0` - `G(3)` выполняет `G(2) + F(1)` - `G(2)` выполняет `G(1) + F(0)` - `G(1)` выполняет `G(0) + F(-1)` - `G(0)` возвращает 1 - `F(-1)` возвращает -1 - Суммируем результаты: `1 - 1 = 0` - `F(1)` возвращает 1 - Суммируем результаты: `0 + 1 = 1` - `G(4)` выполняет `G(3) + F(2)` - `G(3)` выполняет `G(2) + F(1)` (мы уже рассматривали это выше) - `F(2)` выполняет `F(1) + G(0)` (мы уже рассматривали это выше) - Суммируем результаты: `1 + 0 = 1` - Суммируем результаты: `1 + 1 = 2`

Итак, значение `F(6)` равно 2.