Факториал с использованием рекурсии в Java

ИМХО, ключ к пониманию действий, связанных с рекурсией:

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

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

Ключевой момент, который вы здесь упускаете, заключается в том, что переменная «result» является переменной стека, и поэтому она не «заменяется». Для уточнения, каждый раз, когда вызывается факт, в интерпретаторе создается внутренняя переменная NEW, называемая «result», и связана с этим вызовом методов. Это контрастирует с полями объекта, которые связаны с экземпляром объекта, а не с конкретным вызовом метода

public class Factorial {

    public static void main(String[] args) {
        System.out.println(factorial(4));
    }

    private static long factorial(int i) {

        if(i<0)  throw new IllegalArgumentException("x must be >= 0"); 
        return i==0||i==1? 1:i*factorial(i-1);
    }
}

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

Давайте немного изменим исходный код:

int factorial(int n) {
      if (n <= 1)
            return 1;
      else
            return n * factorial(n - 1);
}

Вот подробное вычисление 3! :

Источник: РЕКУРСИЯ (Java, C ++) | Алгоритмы и структуры данных

Сначала вы должны понять, как работает факториал.

Давайте возьмем 4! в качестве примера.

4! = 4 * 3 * 2 * 1 = 24

Давайте смоделируем код, используя приведенный выше пример:

int fact(int n)
    {
        int result;
       if(n==0 || n==1)
         return 1;

       result = fact(n-1) * n;
       return result;
    }

В большинстве языков программирования у нас есть то, что мы называем function stack. Это похоже на колоду карт, где каждая карта помещена над другой - и каждая карта может рассматриваться как функция. Итак, передача по методу fact:

Уровень стопки 1: fact(4) // n = 4 and is not equal to 1. So we call fact(n-1)*n

Уровень стека 2: fact(3)

Уровень стека 3: fact(2)

Уровень стека 4: fact(1) // теперь n = 1. верните 1 из этой функции.

возвращаемые значения ...

Уровень стека 3: 2 * fact(1) = 2 * 1 = 2

Уровень стека 2: 3 * fact(2) = 3 * 2 = 6

Уровень стека 1: 4 * fact(3) = 4 * 6 = 24

, поэтому мы получили 24.

Запишите эти строки:

result = fact(n-1) * n;
           return result;

или просто:

return fact(n-1) * n;

Это вызывает саму функцию. Используя 4 в качестве примера,

По порядку в соответствии со стеками функций.

return fact(3) * 4;
return fact(2) * 3 * 4
return fact(1) * 2 * 3 * 4

Подставляя результаты ...

return 1 * 2 * 3 * 4 = return 24

Надеюсь, вы поняли.