Цикл возврата функции Python

Хорошо, так что этот кусок кода из практического вопроса в моей школе. Мы должны мысленно проанализировать код и проверить ответ.

Когда я впервые разобрал его, я получил 4. Я скопировал код и запустил его через IDLE и получил 8. Я запустил отладчик и увидел, что else: return зациклирует оператор if else до x == 0, а затем он возвращает 1.

Я не понимаю, как возвращается 1 до 8.

def foo(x=5):
    if x == 0:
        return 1
    else:
        return 2*foo(x-1)

print(foo(3))

Я понимаю, что он вызывает foo(x-1) внутри функции foo(x=5), которая заставляет его проверять, есть ли еще снова и снова, до x == 0, затем он возвращает 1. Как возвращает 1 в конечном итоге печать 8?

Ответ 1

Выполните следующие вызовы для foo:

foo(3) -> foo(2) -> foo(1) -> foo(0)

они вернут

foo(0) -> 1
foo(1) -> 2 * foo(0) -> 2 * 1 -> 2
foo(2) -> 2 * foo(1) -> 2 * 2 -> 4
foo(3) -> 2 * foo(2) -> 2 * 4 -> 8

Теперь ясно?

Ответ 2

Я думаю, что у вас есть правильная идея (иначе вы бы не получили ответ 4), вы просто прерываете слишком рано в своем умственном упражнении.

Вы можете отслеживать переменные путем их табуляции при просмотре кода:

foo(3)
- вызывает foo(3 - 1) → foo(2)
  - вызывает foo(2 - 1) → foo(1)
    - вызывает foo(1 - 1) → foo(0)
      - возвращает 1
    - возвращает 2 * foo(1 - 1) → 2
  - возвращает 2 * foo(2 - 1) → 4
- возвращает 2 * foo(3 - 1) → 8

Ответ 3

Рекурсия работает в обратном направлении от того, что вы изначально ожидали. Он не начинается с x = 3, но вместо этого он следует всем рекурсивным вызовам, а первое значение x фактически равно 0.

Вот модифицированная версия вашего script, которая иллюстрирует порядок выполнения шагов и того, как он достиг 8.

def foo(x=5):
    if x == 0:
        r = 1
        print (x, r)
        return r
    else:
        r = 2*foo(x-1)
        print (x, r)
        return r

print(foo(3))

Обратите внимание, как первое значение x, которое было напечатано, равно 1 вместо 3, которые вы ему дали. Как только вы это поймете, вы поймете рекурсию.