Рекурсия - 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 будет первым возвращаемым значением, но оно будет возвращено fac(1), а fac(1) будет возвращено fac(2) и т. Д.

Answer 2

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

Answer 3

Джеймс, когда последний вызов вашей функции (когда 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' будет разорван, возвращение просто завершает одно из нескольких ожидающих выполнения.

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

Если вы вызовете 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). И так далее. Я надеюсь, что это объяснило для вас.