Рекурсия - Python, возвращаемое значение вопроса

Question

Я понимаю, что это может звучать глупо, но в прошлый раз, когда я запрограммировал его, это было на ассемблере, так что мое мышление может быть выключено:

Рекурсивная функция как таковая:

def fac(n):
    if n == 0:
        return 1
    else:
        return n * fac(n - 1)

Почему при достижении функции n == 0 функция возвращает не 1, а ответ, который является факториалом. Я думаю, что-то вроде в ассемблере это будет, когда n == 0:

mov eax, 1
ret

Почему приведенный выше код работает, я полагаю, python возвращает последнее значение в стеке перед этим условием?

Answer 1

Подумайте так, например, для fac (5) , например:

return 5 * fac(4)
           return 4 * fac(3)
                      return 3 * fac(2)
                                 return 2 * fac(1)
                                            return 1 * fac(0)
                                                       1

Таким образом, 1 будет возвращенным значением first , но оно будет возвращено в fac (1) и fac (1) будет возвращен в fac (2) и т. д.

Answer 2

Он действительно возвращает 1, когда n == 0. Это возвращаемое значение выталкивается из стека с вызывающего сайта, который был вызван в n * fac (n - 1) . Это 1 умножается на n , возвращается и т. Д.

Answer 3

Если вы вызовете fac (0), он вернет 1 (не 0, но я полагаю, это просто опечатка в вашем вопросе). Если вы вызовете fac (1), он войдет в предложение else и там будет вызывать fac (0) . Это вернет 1. Затем он вычислит n * 1, который равен 1, и вернет его. Если вы вызовете fac (2) , он также перейдет в предложение else, где вызовет fac (1) , который, как упоминалось выше, вернет 1, поэтому n * fac (n-1) будет равно 2, и это возвращаемое значение fac (2) . И так далее. Я надеюсь, что это объяснило для вас.

Answer 4

Ничего не возвращается неявно - когда n = 0, функция вводит оператор if и возвращает 1 непосредственно из оператора return 1 . Однако это не тот момент, когда ответом является факториал. возвращается пользователю. Вместо этого он может возвращать это значение Функция вызывая , вызываемая fac (1), которая находится в середине ветви n * fac (n - 1) . Таким образом, он будет принимать «1» возвращаем и возвращаем n * 1 , что составляет от 1 до его вызывающей стороны. Если это fac (2), он вернет n * 1 или 2 для вызывающего и т. Д.

Таким образом, fac (5) переводится как:

fac(5) = 5 * fac(4) = 5 * (4 * fac(3) = 5 * (4* (3 * fac(2)) = 5 * (4* (3 * (2 * fac(1)) = 5 * (4* (3 * (2 * (1 * fac(0)) = 5*4*3*2*1*1

Только после того, как значение 1 возвращается через каждый верхний уровень, оно возвращается к первому вызывающему, и умножение на каждом этапе дает вам ответ.

Answer 5

Джеймс, когда последний вызов вашей функции (когда n == 0) возвращает это только один из нескольких случаев fac (n) в стеке вызовов. Если вы скажете print (fac (4)), то по сути это будет стек:

fac(0)
fac(1)
fac(2)
fac(3)
fac(4)
print()

Последний вызов fac (0) соответственно возвращает 1, однако в Python вы запросили возвращаемое значение первого вызова fac (n), fac (4).

Не думайте об этом как о цикле, в котором 'ret' будет разорван, возвращение просто завершает одно из нескольких ожидающих выполнения.