Проблемы с рекурсией с использованием Python 3

Question

Вопрос в том, что делает python во время рекурсии. Я получаю понятие, но кажется, что явный в цикле неявный в рекурсивном алгоритме. Я видел примеры, где рекурсия будет проходить через, а затем шаг назад, чтобы получить ответ. Который я не получаю. Это как код, который я не писал.

Я не могу помочь 'видеть' return return вернуть уравнение вместо здание уравнение и ответ.

Есть несколько примеров рекурсии, которые имеют смысл, но алгоритмы Фибоначчи и факториала сбивают с толку. (Отказ от ответственности: Я не хочу урок Фибоначчи или факториала^_ ^.)

def main(): 
    num = int(input("Please enter a non-negative integer.\n")) 
    fact = factorial(num) 
    print("The factorial of",num,"is",fact) 

def factorial(num): 
    if num == 0: 
     return 1 
    else: 
     return num * factorial(num - 1) 

main() 

если мы делаем 10, я не могу помочь, но думаю, что он должен возвращать результат каждого из этих уравнений и петли! над этим. Я не уверен, как работает python в памяти. Или, как он знает, что она должна вернуть значение 10 * 9 * 8 * 7 * 6 ... и т.д.

вместо возвращения возврата 10 * (10 - 1) возвращение 9 * (9 - 1) return 8 * (8 - 1)

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

Рассматривает ли я меня прямо в лицо или что-то, чего я просто не знаю?

Answer 1

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

Забудьте о инструкции на минуту, и думать о функции факториала в наиболее абстрактной форме:

X    Y 
-------------------- 
0 ------> 1 
1 ------> 1 
2 ------> 2 
3 ------> 6 
4 ------> 24 
5 ------> 120 
6 ------> 720 
... 

Не беспокойтесь сейчас о том, как вычислить это. Подумайте только об абстрактном картографии. Теперь давайте подумаем о том, как сделать рекурсивную версию этой функции. Что нам нужно? Ну, нам нужна функция, которая создает другое сопоставление, а не отображение от [1, 2, 3, ...] к факториалам, а отображение от одного значения от Y к следующему. Другими словами (с использованием нижнего регистра в настоящее время):

x    y 
-------------------- 
1 ------> 1 
1 ------> 2 
2 ------> 6 
6 ------> 24 
24 ------> 120 
120 ------> 720 
720 ------> 5040 
... 

Теперь давайте подумаем о том, как рассчитать это. Сразу появляется проблема: 1 карты до 1 в первый раз и до 2 второй. Поэтому мы знаем, что нам нужно написать специальный случай, чтобы отличить эти два. Но для остальных это довольно просто, не так ли? Просто умножьте x на свою позицию в списке. Таким образом, это означает, что для всех этих частей отображения, нам нужно знать только две вещи: x и его position в списке:

def factorial_recurrence(x, position): 
    return x * position 

Обратите внимание, что эта функция теперь имеет два аргумента, так что это на самом деле немного отличается функция, чем выше:

x, p    y 
------------------------ 
1 0 ------> 1 
1 1 ------> 2 
2 2 ------> 6 
6 3 ------> 24 
24 4 ------> 120 
120 5 ------> 720 
720 6 ------> 5040 

Это показывает совершенно ясно, как мы можем различать два отображений из 1. Теперь нам просто нужно придумать способ получить информацию о позиции. Так получилось, что position совпадает с значением X. Таким образом, один простой способ - использовать цикл. Здесь мы заботимся о X == 0, просто установив x в 1 и начать наш цикл в 1 вместо 0:

def factorial(X): 
    x = 1 
    for position in range(1, X + 1): 
     x = factorial_recurrence(x, position) 
    return x 

Теперь обратите внимание, что стоимость x здесь находится передаются в factorial_recurrence, а затем результат сохраняется как x.

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

Это рекурсия!

Это, в критическом смысле, уже рекурсивный алгоритм. Это просто, что представление здесь наизнанку, и функция также включает в себя информацию position из-за рекурсивного процесса.Для того, чтобы увидеть, что я имею в виду, посмотрите на это:

def even_factorial(X): 
    x = 1 
    for position in range(2, X + 1, 2): 
     x = factorial_recurrence(factorial_recurrence(x, position - 1), position) 
    return x 

Это дает тот же результат, как и factorial для каждого четного значения X. (Он дает результат X - 1 для нечетных значений X.) И нам не нужно останавливаться на достигнутом. Мы можем сделать то же самое для каждого третьего значения X (вспыхивают вложенности для ясности):

def third_factorial(X): 
    x = 1 
    for position in range(3, X + 1, 3): 
     x = factorial_recurrence(
       factorial_recurrence(
        factorial_recurrence(
         x, 
         position - 2 
        ), 
        position - 1 
       ), 
       position 
      ) 
    return x 

Теперь сделайте то же самое для каждого 4-го, каждый 5-й, и так далее. Если вы продолжите этот процесс, то для любого заданного X вы в конечном итоге создадите функцию, которая не вернет ничего, кроме 1, до тех пор, пока вы не пройдете X, а затем, когда вы пройдете X, вы получите факториал X.

На данный момент трюк рекурсии состоит в том, чтобы понять, что мы можем автоматизировать этот процесс выключения петли наизнанку, получив вызов factorial. Каждый раз, когда вызывается factorial, он просто гнездится еще один вызов factorial_recurrence внутри последнего - если только X не равен 0, и в этом случае он возвращает 1, завершая последовательность вложенных вызовов.

def factorial(X): 
    if X == 0: 
     return 1 
    else: 
     return factorial_recurrence(factorial(X - 1), X) 

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

Answer 2

Подумайте об этом как о математической проблеме. Если вы знаете ответ на !9, как бы вы вычислили !10? Вам просто нужно умножить значение !9 на 10.

Это именно то, что делает рекурсивная функция; он просто выражает факториал num как то же, что и num раз факториал num - 1. Единственным номером, для которого это не работает, является 0, но факториал 0 известен, это 1.

Итак, факториал 10 в основном:

• 10 * factorial(9) ==
• 10 * 9 * factorial(8) ==
• 10 * 9 * 8 * factorial(7) ==
• 10 * 9 * 8 * 7 * factorial(6) ==
• 10 * 9 * 8 * 7 * 6 * factorial(5) ==
• 10 * 9 * 8 * 7 * 6 * 5 * factorial(4) ==
• 10 * 9 * 8 * 7 * 6 * 5 * 4 * factorial(3) ==
• 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * factorial(2) ==
• 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * factorial(1) ==
• 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * factorial(0) ==
• 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 1

Обратите внимание, что каждый factorial() вызов получает новый набор переменных. Не происходит перезаписи; это новый, новый вызов функции. Значение num в каждом вызове полностью не зависит от всех других вызовов функции.

Если это помогает, попробуйте использовать ноутбук для отслеживания информации о функции. Запишите переменные на странице, обновив их при прохождении кода вручную. Для каждый новый вызов функции, переверните страницу и начните с следующего листа бумаги, записывая там переменные. Вы напишете 10 по первой, затем 9 (num - 1) на второй странице и т. Д. Возвращаемое средство принимает возвращаемое значение, вырывает страницу из ноутбука и возвращает страницу в блокноте, чтобы обновить переменные там с этим возвращаемым значением.

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

Также, Python не ухаживает за, вы используете эту функцию здесь повторно. Вы могли бы создать 11 отдельных функций, каждая с отдельным именем и отдельным num имя:

def factorial10(num10): 
    if num10 == 0: 
     return 1 
    else: 
     return num10 * factorial9(num10 - 1) 

def factorial9(num9): 
    if num9 == 0: 
     return 1 
    else: 
     return num9 * factorial8(num9 - 1) 

def factorial8(num8): 
    if num8 == 0: 
     return 1 
    else: 
     return num8 * factorial7(num8 - 1) 

# ... 
# etc. all the way to 

def factorial0(num0): 
    if num0 == 0: 
     return 1 
    else: 
     return num0 * factorialminus1(num0 - 1) 

и Python не видит никакой разницы между этими функциями и оригиналом. Точная же работа будет выполнена, но вместо повторного использования одной и той же функции вы используете другой функциональный объект с идентичным поведением . Изменены только имена.

Итак, рекурсия - это всего лишь умный способ объединить целую серию вызовов функций. Эти вызовы функций являются раздельными, им не важно, что делают локальные переменные других функций. Python не должен «ничего знать», он просто должен выполнить эту функцию для вас, и когда она встречается с другим вызовом функции, выполните этот вызов функции и используйте возвращаемое значение. То, что эта функция является той же самой функцией или другой, не имеет никакого значения.