Факториальные вычисления с использованием метода рекурсивного метода

Question

Этот код из книги: «C# 5.0 в двух словах» и является образцом LinqPad. На странице 39 написано:

«Этот метод является рекурсивным, а это означает, что он называет себя каждый раз, когда метод ввода, новый ИНТ выделяется в стеке, и каждый раз, когда метод выходит, то ИНТ . перераспределена «.

Используя буквенные 5 выходов и ответ на 120 (3 выходов 6)

Может кто-нибудь объяснить, как это работает? Я программист VB, пытающийся изучить C# и хотел бы понять конструкции вроде этого. Я прошел через него много раз и не могу понять, что происходит после x == 0 и возвращается 1. До x равно нулю, поток выполнения легко понять. После этого последний оператор возврата, как представляется, многократно выполняется (магически) до тех пор, пока x не вернется к исходному значению, а затем вернется к точке, где он был первоначально вызван, и выдает вышеупомянутый (магический) числовой результат.

static void Main() 
{ 
    Console.WriteLine (Factorial(5)); 
} 
static int Factorial (int x) 
{ 
    if (x == 0) return 1; 
    return x * Factorial (x-1); 
} 

Answer 1

Это рекурсивное, потому что это утверждение здесь:

return x * Factorial (x-1); 

возвращает результат х * результат вызова Факториал (X-1) ... Это, называющие себя, чтобы получить ответ. Он вырывается из цикла, когда x == 0, просто возвращая значение 1.

Но одно замечание, кому х == 0 возвращает значение? Ответ, скорее всего, представляет собой цикл, который накапливает значения.

Answer 2

Метод факторный снова вызывает себя, начиная с 5, и уменьшает аргумент (х-1), до тех пор, переданный аргумент х не равен 0.

Таким образом, первый вызов Factorial проходит 5, второй вызов 4 , 3, 2, 1, 0.

И математика сделать это: 5 * 4 * 3 * 2 * 1 = 120.

Answer 3

Что это делает, называющим себя несколько раз.

Что происходит, так это следующее.

Входит Факториал с х равными 5 и с тех пор мы больше 0 умножат наши 5 с результатом вызова нашего самоуправления (факториал) снова 5 - 1, который 4. Внутри этого рекурсивных мы называем находят, что мы сами делаем еще один рекурсивный вызов с 4 - 1, который равен 3. Мы делаем это несколько раз, пока не назовем Factorial с 0, где он возвращает 1. Затем он возвращается к рекурсии, которая умножает ее на 2, которая возвращается к рекурсии, которая умножает его на 3, а затем следующий на 4, а затем следующий на 5.

В конце концов вы вернуть результат 1 * 2 * 3 * 4 * 5, которое 120.

Answer 4

Call Factorial(3) (which returns 3 * 2) 
    x doesn't == 0 
    return 3 * Factorial(2) 
      Calls Factorial(2) (which returns 2 * 1) 
       x doesn't == 0 
       return 2 * Factorial(1) 
          Calls Factorial(1) (which returns 1 * 1) 
          x doesn't == 0 
          return 1 * Factorial(0) 
             Calls Factorial(0) (which returns 1) 
             x == 0 so return 1 

Важным моментом является то, что рекурсивная функция должна иметь условие завершения, иначе она будет называть себя бесконечно (пока не закончится пространство стека). В вашем примере if (x == 0) return 1; является условием завершения. Так как функция вызывает себя со значением параметра, меньшим, чем он был вызван, в конечном итоге он в конечном итоге вызовет себя с 0, и именно тогда закончится рекурсия.

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

Answer 5

Существует призыв к возврату для каждого вызова Factorial. Это рекурсивные вызовы размотки после й == 0.

Я думаю, что это может быть проще, чтобы увидеть, если вы немного изменить код, если только временно:

static int Factorial (int x) 
{ 
    if (x == 0) return 1; 
    else 
    { 
     int y = x * Factorial (x-1); 
     return y; 
    } 
} 

Answer 6

Понятие рекурсии на самом деле не ограничены на любой конкретный язык. Идея этого в том, что функция вызывает себя.

Давайте рассмотрим ваш пример: факториальная функция. Но сейчас давайте отложим реализацию и рассмотрим ее в более абстрактных терминах. Функция состоит из двух элементов:

i) Инструкция по вычислению элемента 'n'.

II) Инструкция, как рассчитать начальный элемент

Так как же мы вычислим элемент n для факториала? Мы n и умножить его на факториал предыдущего элемента: n-1:

п * Факториал (п-1)

И есть только один начальный пункт: 0. То есть, когда n == 0 результат 1 или другими словами Factorial(0) дает 1.

алгоритм значение содержит действительно этих двух шагов

if (x == 0) 
    return 1;      // Do this when calculating Factorial of 0 
else 
    return x * Factorial (x-1); // Do this when calculating an element n 

Ok. Теперь, что происходит, когда мы хотим рассчитать факториал 4? Давайте перейдем к конкретным шагам.

Factorial(4) -> 4 * Factorial(4-1) -> 4 * Factorial(3)

Мы вызывается факториал 4. Поэтому умножим 4 на факториал 4-1. Для того, чтобы получить факториал 4-1 снова вызвать функцию факториала:

Factorial(3) -> 3 * Factorial(3-1) -> 3 * Factorial(2)

Теперь нам нужно вычислить факториал 2.

Factorial(2) -> 2 * Factorial(2-1) -> 2 * Factorial(1)

И из 1

Factorial(1) -> 1 * Factorial(1-1) -> 1 * Factorial(0)

Обратите внимание, что теперь мы должны вычислить факторный номер 0. Но здесь мы имеем ve специальная инструкция: если аргумент равен 0, результат должен быть равен 1. Давайте вернем наши расчеты:

Factorial(0) is 1. Замените результат вычисления для факториала 1.

Factorial(1) -> 1 * Factorial(1-1) -> 1 * 1 который также 1

Factorial(2) -> 2 * Factorial(1) -> 2 * 1 -> 2

Factorial(3) -> 3 * Factorial(2) -> 3 * 2 -> 6

Factorial(4) -> 4 * Factorial(3) -> 4 * 3 -> 12

Вы упомянули следующее объяснение:

Каждый раз, когда метод вводится, н ew int выделяется в стеке, и каждый раз, когда метод завершается, int освобождается.

Этих шагов, когда мы идем в Factorial функции для вычисления факториала для предыдущего числа, когда новый ИНТ должен быть выделен в стеке: для факториала 4 числа 4 помещается в стеке и алгоритм вычисляет факториал из 3 и т. д. И когда мы дойдем до самого конца, то есть с факториалом 0, мы можем, наконец, начать освобождать номера. Мы имеем факториал 0, умножим результат на 1. Факториал 1 возвращается и 1 освобождается. То же самое происходит для 2, 3 и, наконец, 4.

Надеюсь, что прояснилось целое понятие немного. Я знаю, что объяснение обширно, но, с другой стороны, сложно понять его с самого начала, поэтому я предпочел быть слишком тщательным.

Answer 7

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