Поток факториальной функции с использованием рекурсии

Question

Я изучаю основы Python прямо сейчас, читая Thinking Python .

Когда я читал главу о «плодотворной» функции, то есть функции, которая «возвращает» значение, я столкнулся с этой проблемой. Я могу более или менее понять, как работает код факториальной функции, но не совсем так. У меня проблемы с пониманием того, как именно происходит выполнение функции, связанной с самовозвратом или рекурсией. Кстати, данные принтера в коде, показанном ниже, являются лесами, устройством, используемым для отслеживания выполнения функции.

Без лишних слов, вот код.

def factorial(n):
    space=' '*(2*n)
    print(space, 'factorial', n)
    if n==0:
        print(space, 'returning 1')
        return 1
    else:
        recurse = factorial(n-1)
        result=n*recurse
        print(space, 'Returning', result)
        return result

factorial(3) 

Результат или вывод этого кода потрясающе v-образный. Я, по жизни, не могу понять, почему компьютер (или компилятор?) Запускает программу так, как здесь. Кажется, что он сначала печатает первую строку и последнюю строку, а затем переходит к печати второй строки и второй до последней строки ... Это странно. Вы ожидаете, что это всегда идет сверху вниз.

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

def f(n):
    print(n)
    if n==0:
        return 0
    else:
        print(3*n)
        f(n-1)
        return

Буду очень признателен, если вы поможете мне с этим!

Answer 1

Что может вас смущать, так это то, что рекурсивный вызов не происходит в конце функции, как в случае с вашим примером f(). Это означает, что у вас есть код, который выполняется перед входом в код рекурсии и , который выполняется после выхода из рекурсии . Давайте посмотрим, что происходит в factorial:

Рекурсивный шаг
Выберите любой рекурсивный шаг i, который вам нравится, который не является базовым. А затем посмотрите, что делает функция, не выполняя рекурсию.

Для вашей функции factorial давайте возьмем вызов factorial(i), где i отличается от 0. Этот призыв делает три вещи:

1. print 2*i пробелы и "factorial i"
2. факториал вызова (i-1)
3. печать 2*i пробелы и "возвращение я"

Итак, результат будет:

(2*i spaces) factorial i
# everything factorial(i-1) outputs
(2*i spaces) returning i

Вы увидите, что вывод factorial(i-1) зажат между выводами factorial(i). Чтобы выполнить рекурсию, все, что вам нужно сделать, это взорвать шаблон. Давайте сделаем еще один шаг i-1 во внимание:

(2*i spaces) factorial i
(2*(i-1) spaces) factorial i-1
# everything factorial(i-1) outputs
(2*(i-1) spaces) returning i-1
(2*i spaces) returning i

Итак, вы видите, что отступ уменьшается с вызовами, так как i уменьшается, что составляет v-shape .

Базовый корпус
Он просто печатает

factorial 0
returning 1

Собираем все вместе
Теперь вы можете найти словесное выражение для того, что factorial(i) делает: factorial(i) производит вывод v-формы

      factorial i
    factorial i-1
  ...
factorial 0
returning 1
  ...
    returning i-1
      returning i

Если это верно для случая i == 0, заключите оттуда, что это верно для i+1, если вы предполагаете, что это верно для i, используя список в разделе рекурсивный шаг, Сделав это, вы можете быть уверены, что factorial(n) работает для любого n >= 0.

Answer 2

Ваш код немного реструктурирован, чтобы его было легче увидеть:

def factorial(n):
    space = ' '*(2*n)
    print(space, 'factorial', n)
    result = 1 if n == 0 else n*factorial(n-1)        
    print(space, 'Returning', result)
    return result

И это вывод для factorial(3) с "V-образной формой", которую вы упомянули:

       factorial 3
     factorial 2
   factorial 1
 factorial 0
 Returning 1
   Returning 1
     Returning 2
       Returning 6

Выглядит правильно и выполняет работу по вычислению факториала. Чтобы понять порядок отпечатков, представленных здесь, подумайте о следующем:

• Печать начинается с вызова 3, поскольку это ваша точка входа
• Тогда отступ равен 3x2 = 6 пробелам
• Так как для вычисления factorial(3) необходим возврат factioral(2), следующий вызов идет с отступом 2x2 = 4 пробелов. И так далее для всех дальнейших факториалов. Вот откуда взялась V-образная форма первой половины отпечатков.
• Все эти вызовы функций теперь «ждут» возврата результата в позиции рекурсивного вызова в коде. Поскольку только factorial(0) может доставить это возвращаемое значение без другой рекурсии, оно напечатает первое возвращаемое значение. С отступом 0.
• При указанном выше возвращаемом значении вызов функции factorial(1) теперь может вычислить свой результат путем умножения возвращенного 1 на его собственный n, что дает 1. Это следующий отпечаток с отступом 2.
• И так далее для всех высших шагов рекурсии, изнутри наружу. И вот как формируется вторая половина V-образной формы.

Важно понять, что значения результатов функций (и, тем самым, печати) могут появляться только в КОНЦЕ полного дерева рекурсии, которое находится под ним. Вот почему вызов print factorial 3 находится в первой строке, а соответствующий Returning 6 print - в последней строке - после завершения всего внутреннего дерева.

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

РЕДАКТИРОВАТЬ: бесконечная рекурсия

В качестве ответа на ваш вопрос, вот пример, который показывает, как каждый рекурсивный вызов функции будет иметь свою собственную область видимости переменных и, следовательно, не знать о переменных, установленных в другом экземпляре той же функции, заканчивающихся на RecursionError когда максимальная глубина рекурсии стека вызовов достигнута.

def foo():
    try:
        print("a = ", a)
        return   #  break out of loop
    except UnboundLocalError:
        print("no variable a. defining one now.")
        a = 3          
        foo()    #  try again

foo()