Факторизовать число с помощью рекурсии

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

1. вызовите factorialize (5);
2. первый шаг рекурсии возвращается -> 5 * факториализация (4)

   current value: 5 * factorialize(4)

3. второй шаг рекурсии возвращается -> 4 * факториализация (3)

   current value: 5 * 4 * factorialize(3)

4. третий шаг рекурсии возвращает -> 3 * факториализация (2)

   current value: 5 * 4 * 3 * factorialize(2)

5. четвертый шаг рекурсии возвращает -> 2 * factorialize (1)

   current value: 5 * 4 * 3 * 2 * factorialize(1)

6. шестой шаг рекурсии возвращает -> 1 * факториализация (0)

   current value: 5 * 4 * 3 * 2 * 1 * factorialize(0)

7. седьмой (последний) шаг рекурсии возвращается -> 1

   current value: 5 * 4 * 3 * 2 * 1 * 1

В результате получается 120.

function factorialize(num) {
  if (num === 0) { return 1; }      // 7th step
  return num * factorialize(num-1); // 1st to 6th step
}

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

function factorialize(num) {
  let factorial = 1; // base case, equivalent to fact(0)

  for (let i = 1; i <= num; i++) { // multiply for each number from 1 to n
    factorial *= i;
  }

  return factorial;
}

console.info(factorialize(5));

Рекурсивная функция работает точно так же. fact(n) - это исходный вызов, но для вычисления fact(n) он должен сначала вычислить факториал n - 1. fact(n - 1) невозможно вычислить без fact(n - 2). Каждая функция помещается в стек вызовов, ожидая разрешения функций над ней. В конце концов будет вызван fact(0), и мы знаем, что это 1 на основе рекурсивное определение факториала. fact(0) называется базовый вариант и не выполняет никаких рекурсивных вызовов. Без базового случая n становится все меньше и меньше, пока в стеке не закончится место, что приведет к сбою программы.

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

Если это все еще не имеет смысла, бросьте console.info(), чтобы просмотреть каждый шаг на этом пути:

function factorialize(num) {
  if (num === 0) { // base case 
    console.info("fact(0) returning 1");
    return 1; 
  }

  // recursive case
  const result = num * factorialize(num - 1);
  console.info("fact(" + num + ") returning " + result);
  return result;
}

console.info(factorialize(5));