Рекурсивный цикл (C #)

Question

Может кто-нибудь, пожалуйста, объясните мне это? Я написал функцию для вычисления факториала числа в C #:

public int factorial(int input)
{
    if (input == 0 || input == 1)
        return 1;
else
{
    int temp = 1;
    for (int i = 1; i <= input; i++)
        temp = temp * i;
    return temp;
    }
}

Но я нашел некоторый код C ++ (я точно не знаю, кстати, C ++), который находит факториал с использованием рекурсивного цикла:

int factorial(int number) {
 int temp;
 if(number <= 1) return 1;
 temp = number * factorial(number - 1);
 return temp;
}

Может кто-нибудь объяснить мне, как это работает? Спасибо.

Answer 1

Ну, он использует тот факт, что factorial(n) равен n * factorial(n - 1) с базовым регистром n = 1.

Так, например:

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

Реализация просто использует это рекурсивное определение.

Answer 2

Синтаксически код C ++ идентичен тому же коду, написанному на C #.Не позволяйте языковым несоответствиям застать вас врасплох!На самом деле это выглядит как C, учитывая, что переменная объявлена ​​в верхней части функции;это не обязательно в C ++ или C #.Я предпочитаю объявлять переменные при первом их использовании, объединяя объявление и инициализацию в одном выражении, но это всего лишь стилистическое предпочтение, которое не меняет функции кода.

Я постараюсьобъясните это, добавив комментарии к каждой строке фрагмента кода:

// Declare a function named "Factorial" that accepts a single integer parameter,
// and returns an integer value.
int Factorial(int number)
{
    // Declare a temporary variable of type integer
    int temp;

    // This is a guard clause that returns from the function immediately
    // if the value of the argument is less than or equal to 1.
    // In that case, it simply returns a value of 1.
    // (This is important to prevent the function from recursively calling itself
    // forever, producing an infinite loop!)
    if(number <= 1) return 1;

    // Set the value of the temp variable equal to the value of the argument
    // multiplied by a recursive call to the Factorial function
    temp = number * Factorial(number - 1);

    // Return the value of the temporary variable
   return temp;
}

Рекурсивные вызовы просто означают, что функция вызывает себя из одной и той же функции.Это работает, потому что факториал n эквивалентен следующему утверждению:

n! = n * (n-1)! 

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

Answer 3

Давайте проанализируем эту строку построчно:

if(number <= 1) return 1;
temp = number * factorial(number - 1);
return temp;

Строка 1: если число меньше или равно нулю, мы возвращаем 1. Это означает, что 0! = 1 и 1! = 1

Строки 2 + 3: В противном случае мы возвращаем number * factorial(number - 1). Давайте посмотрим на это для 5! (здесь я использую n! как синоним для factorial(n) для краткости)

5!
5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 3 * 1 // Here we don't have to expand 1! in the same way because of the condition

Так что все это расширяется. Это просто используя свойство, которое

n! = n * (n - 1) * ... * 2 * 1 = n * (n - 1)!

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

Answer 4

Рекурсивные функции - это вызовы функций из одной и той же функции

например:

  Test()
    {
      i++;
      Test();
      cout<<i;
    }

посмотрите код, который будет вызывать функцию снова и снова

Проблема с рекурсиейон будет работать бесконечно, поэтому хотите остановить его определенным условием

некоторые изменения в приведенном выше коде теперь выглядят

int i=0; 
Test()
        {
         if(i==10) return;
         i++;
         Test();
         cout<<i;
        }

вывод будет напечатан 10 раз 10 раз, здесь эта строка cout<<i; будетвыполнить после возврата

Answer 5

Рекурсивная функция - это функция, которая вызывает себя в своем теле. Чтобы он был ограничен и в конечном итоге возвращал значение, должны произойти две вещи:

1. У него должен быть базовый случай, когда он не вызывает себя снова, возвращая известное значение. Этот базовый случай останавливает рекурсию. Для факториальной функции это значение равно 1, когда вход равен 0.

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

Более простой способ взглянуть на эту функцию таков (действителен только для положительного ввода):

int factorial(int input) {
  return input == 0 ? 1 : input * factorial(input - 1);
}