Блог

Я действительно пытаюсь разобраться в том, как работает рекурсия, и понять рекурсивные алгоритмы. Например, приведенный ниже код возвращает 120, когда я ввожу 5, извините за мое невежество, и я просто не понимаю, почему?

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

answer = int (raw_input('Enter some number: '))

print fact(answer)
 

давайте пройдемся по выполнению.

 fact(5):
   5 is not 0, so fact(5) = 5 * fact(4)
   what is fact(4)?
fact(4):
   4 is not 0, so fact(4) = 4 * fact(3)
   what is fact(3)?
fact(3):
   3 is not 0, so fact(3) = 3 * fact(2)
   what is fact(2)?
fact(2):
   2 is not 0, so fact(2) = 2 * fact(1)
   what is fact(1)?
fact(1):
   1 is not 0, so fact(1) = 1 * fact(0)
   what is fact(0)?
fact(0):
   0 IS 0, so fact(0) is 1
 

Теперь давайте соберем наш результат.

 fact(5) = 5* fact(4)
 

замените в нашем результате факт (4)

 fact(5) = 5 * 4 * fact(3)
 

замените в нашем результате факт (3)

 fact(5) = 5 * 4 * 3 * fact(2)
 

замените в нашем результате факт (2)

 fact(5) = 5 * 4 * 3 * 2 * fact(1)
 

замените в нашем результате факт (1)

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

замените в нашем результате на fact(0)

 fact(5) = 5 * 4 * 3 * 2 * 1 * 1 = 120
 

И вот оно. Рекурсия — это процесс разбиения более крупной проблемы, рассматривая ее как успешно меньшие проблемы, пока вы не дойдете до тривиального (или «базового») случая.

Разбейте проблему на этапы ее выполнения.

 fact(5)
| 5  * fact(4)
|| 5 * (4 * fact(3))
||| 5 * (4 * (3 * fact(2))
|||| 5 * (4 * (3 * (2 * fact(1))))
||||| 5 * (4 * (3 * (2 * (1 * fact(0)))))
|||||| 5 * 4 * 3 * 2 * 1 * 1
120
 

Ваша функция просто вызывает саму себя, так же, как ее может вызвать любая другая функция. Однако в этом случае вашей функции нужна точка остановки, чтобы она не повторялась бесконечно (вызывая переполнение стека!). В вашем случае это когда n равно 0 (вероятно, вместо этого должно быть 1).

Имейте в виду, что каждый вызов fact(), независимо от того, вызывается ли он извне или вызывается сам по себе, получает свой собственный отдельный набор локальных переменных.

 fact(1) has n of 5
   fact(2) has n of 4
      fact(3) has n of 3
         fact(4) has n of 2
            fact(5) has n on 1
               fact(6) has n of 0
 

Самые глубокие из них (здесь, fact(6) самые глубокие) вычисляются полностью до того, как уровни над ними в стеке вызовов смогут завершиться.

Итак

• fact(6) возвращает значение 1 fact(5) (случай завершения).
• fact(5) возвращает значение 1 в fact(4) (1 * 1)
• fact(4) возвращает 2 в fact(3) (2 * 1)
• fact(3) возвращает 6 в fact(2) (3 * 2)
• fact(2) возвращает 24 в fact(1) (4 * 6)
• и, наконец fact(1) , возвращает 120 (5 * 24) своему вызывающему, что бы это ни было.

Рекурсивная функция — это функция, которая вызывает саму себя и продолжает делать это до завершения вычисления и получения результата. Ключ с приведенной выше функцией факториала — это возвращаемый x * факт (x-1)

Итак, если вы введете 5, он выполнит 5 * факт (5-1) * факт 4-1) …. И так далее, пока он не достигнет 0, а затем вернет 1. Итак, у вас будет 5*4*3*2*1 то есть 120.

Он продолжает распределять переменные в стеке. Поэтому, если вы введете слишком большое число, это может привести к исключению переполнения стека. Если вы не используете что-то, называемое оптимизацией конечных вызовов (TCO), которая превращает рекурсивную функцию в цикл for и очищает выделенную память.