Невозможно понять рекурсивный факториал

Question

Я новичок в рекурсивном, и мне трудно понять, как рассчитывается эта рекурсивная факторная функция.

Когда я пытаюсь запустить через код с моей точки зрения, это, как я себе это:

Если число = 4,

первого возвращения: 4 х 3

второе возвращение : 3 х 2

третье возвращение: 2 х 1

Таким образом, в мой разум - это (4 x 3) * (3 x 2) * (2 x 1), но, очевидно, правильный возврат будет 4 X 3 X 2 X 1. Я хочу, чтобы быть в состоянии понять, как это получить 4 X 3 X 2 X 1.

public static long factorial(long number) { 
     if (number <= 1) 
      return 1; 
     else 
     { 
      System.out.println(number + " x " + (number-1)); 
      return number * factorial(number - 1); 
     } 
    } 

Любая помощь и объяснение было бы весьма признателен.

Answer 1

Ваша визуализация должна быть:

Если число = 4,

первого возвращения: 4 х (второе возвращение)

второе возвращение: 3 х (третье возвращение)

3-й возврат: 2 x (4-й возврат)

4-й возврат: 1

Это упрощает до 4 x 3 x 2 x 1, как и ожидалось.

В принципе, вам нужно различать «возвращаемое значение x» и «возвращать результат рекурсии, передавая значение x».

Answer 2

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

Каждая итерация факториала должна ждать следующих итераций, прежде чем она вернет значение.

Фактическая операция, выполняемая 1 * 2 * 3 * 4, а не 4 * 3 * 2 * 1. Значения возвращаются с последнего на первое.

Answer 3

Часть проблемы заключается в том, что ваш оператор печати является ложью. Измените его на

System.out.println("factorial(" + number + ") = " + number + " x factorial(" + (number-1) + ")"); 

чтобы посмотреть, что на самом деле происходит. Затем рассмотрим, как ваша печатная продукция напоминает математическое определение, которое

 | n * (n-1)!  for n > 1 
n! = | 
    | 1    for n == 0,1. 

Я обнаружил, что это помогает понять рекурсивные функции, как, ну, функции. Одним из больших преимуществ функций является то, что они инкапсулируют свои вычисления, скрывая конкретные детали. Это приводит к «рекурсивному скачку веры» —, если бы у вас была функция, которая возвращала факториал (n-1), независимо от того, как он ее выполнил, было бы легко использовать его для вычисления factorial (n) на основе математического повторения определение.Доверяя, что функция будет работать, она (почти) тривиальна для записи функции!