Как работает эта рекурсивная функция в Python?

Question

Я изучаю питон из книги: «ThinkPython».

На странице 56 (Глава 6. Плодотворные функции) существует рекурсивная функция, которая вычисляет факториал любого числа. Это действительно работает, однако я не понимаю, почему. Это код:

def factorial(n): 
    if n == 0: 
     return 1 
    else: 
     recurse = factorial(n-1) 
     result = n * recurse 
     return result 

Скажем, я пытаюсь с 3, я думаю, это то, что должно произойти:

1. входит в функцию факториала и п = 3
2. входит утверждение еще потому, что п не 0
3. и здесь восходит к началу к шагу 1 при п = 2

так он должен сделать то же самое до n = 0 и возвращает 1 (он никогда не дойдет до последних строк).

Answer 1

Вы правы, насколько можете. Однако вы не продолжаете достаточно далеко. Когда возвращается факториал (0), куда он возвращается? он возвращается к

recurse = factorial (n - 1) 

линии, где n = 1, а затем продолжить оттуда. Итак, recurse = 1, result = 1* 1 = 1 и возвращает 1. Снова, это идет к строке recurse = в case n = 2. result = 2*1 = 2 и возвращает это, в строку recurse =, где n = 3, поэтому result = 2 * 3 = 6, что что возвращается.

Answer 2

Факториал n не определяется как n * (n-1) * (n-2) и т.д., пока 1

Так для n = 5 -> 5*4*3*2*1

В коде факториал определяется как n * whatever the factorial of n-1 is

Python будет узнать эту последнюю часть, задавая себе: Что такое факториал n-1? Ну это (n-1) * whatever the factorial of (n-1)-1 есть.

Вы видите цикл/рекурсию?

Поскольку для n==0 факторный вернется 1, питон может спросить себя снова и снова, что рекурсивная часть, пока она не попросит себя, what is the factorial of 0?. Эта часть жестко запрограммирована в первой части.

Как только он входит в эту последнюю часть, он знает и другие ответы тоже! Для n == 5:

• Факториал 5 * (факториал 4)
  • факториал равен 4 * (факториал 3)
    • ...
      • факторного 0 равно 1.

Факториал 5 = 5 * 4 * 3 * 2 * 1

Answer 3

Ваша функция:

def factorial(n): 
if n == 0: 
    return 1 
else: 
    recurse = factorial(n-1) 
    result = n * recurse 
    return result 

Поедем через исполнение эта функция шаг за шагом, начиная с n = 3.

Entering 
STATE 1 
n = 3 
recurse = factorial(3-1) 

STATE 2 
n = 2 
recurse = factorial(2-1) 

STATE 3 
n = 1 
recurse = factorial(1-1) 

STATE 4 
You now have an n = 0, so you return 1 to STATE 3. 

STATE 3 
n = 1 
recurse = 1 
result = 1 
return result to STATE 2 

STATE 2 
n = 2 
recurse = 1 
result = 2 * 1 = 2 
return result to STATE 1 

STATE 1 
n = 3 
recurse = 2 
result = 3 * 2 = 6 

А потом 6, факториал 3, возвращается в вызывающую функцию: D

Рекурсия действительно сложная вещь, чтобы противостоять, это только занимает время, чтобы привыкнуть к нему и различным способам, что это может быть использован.