Рекурсивные функции - факториалы

Question

Я пытаюсь обернуть голову вокруг примера факториального вычисления для рекурсивных функций, я всегда теряюсь, когда пытаюсь отследить поток самой рекурсивной функции.Возвращает ли оно значение для * (a - 1) для каждой итерации?Почему он не возвращает значение 1?Простые слова только плз newb здесь:)

// factorial calculator
#include <iostream>
using namespace std;

long factorial (long a)
{
  if (a > 1)
   return (a * factorial (a-1));
  else
   return 1;
}

int main ()
{
  long number = 9;
  cout << number << "! = " << factorial (number);
  return 0;
}

Answer 1

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

когда a <= 1, возвращается 1 </p>

Рекурсивная функция опирается на стек, когда вы вызываете factorial (9), функция на самом деле говорит: «Ой, у меня пока нет ответа, но я знаю, что factorial (9) на самом деле 9 * factorial (9-1) Извините, я сейчас позвоню factorial (8) и подожду, если что-нибудь действительно сработает в будущем "

Затем код в конце концов встретился с factorial (1), затем он останавливается и говорит: «factorial of 1 - это сам 1», он очень хорошо это знает, и я называю это точкой остановки рекурсивной функции.

Answer 2

Хватит пытаться отслеживать все через рекурсивные вызовы и думать о рекурсивной функции как о фактической функции. Иногда случается так, что ты сам себя называешь. Когда вы передаете функции аргумент, вам не нужно знать, что происходит за стеной. Функция - это абстракция для выполняемой работы, которая возвращает правильный ответ на основе своего аргумента. Например, когда вы используете exp() или log() или cos(), вам не нужно знать, как это работает на самом деле, чтобы использовать его.

Именно здесь вы должны совершить рекурсивный скачок веры - «Если я могу доверять этой функции, чтобы дать мне правильный ответ для более мелкой проблемы, то я могу составить ответ для моей текущей проблемы». Для факториалов правильный ответ - 1 для n, равный нулю или единице, и n * factorial(n - 1) для n > 1. Вы можете подтвердить это, написав эту формулировку для небольшого случая:

4! = 4 * 3! = 4 * (3 * 2!) = 4 * (3 * (2 * 1!)) = 4 * (3 * (2 * 1))

Да, это в значительной степени арифметическое определение 4!

Теперь посмотрите на рекурсивную реализацию, которую вы разместили, слегка переупорядоченную, и посмотрите прямую корреспонденцию:

long factorial(long a) {  // If I trust this function...
  if (a <= 1)   // when a is 0 or 1
    return 1;   // I know the answer is 1.
  else          // Otherwise, trust the answer for the smaller case of (a-1) and 
    return (a * factorial(a-1));         // multiply that answer by a to get a!.
}

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

Answer 3

Представьте, что вы переписываете строки кода во время его оценки.Например, предположим, что вы вызываете:

factorial(3)

В функции факториала ваша переменная a имеет значение 3. Таким образом, условие if оценивается как true.Это означает, что весь оператор if можно переписать как return (a * factorial (a-1)), но со значением 3 вместо a.Таким образом, у вас есть:

(3 * factorial (3-1))

В продолжение, 3-1 будет оцениваться, оставляя:

(3 * factorial (2))

Следующим шагом будет оценка вызова на factorial(2).В этом вызове переменная a имеет значение 2, поэтому условие if снова оценивается как истинное и может быть переписано как:

(3 * 2 * factorial(2-1))

Затем вычисляется 2-1, поэтому вы получаете:

(3 * 2 * factorial(1))

Затем оценивается вызов factorial(1).На этот раз a имеет значение 1 и условие if ложно.Это означает, что он может быть переписан как 1:

(3 * 2 * 1)

Затем 3 * 2 оценивается:

(6 * 1)

Затем 6 * 1 оценивается:

(6)

Скобки здесь не имеют значения (но они есть в вашем коде), так что это на самом деле:

 6