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

Я изучаю Java, используя книгу Java: The Complete Reference. В настоящее время я работаю над рекурсией.

Обратите внимание: в stackoverflow есть похожие вопросы. Я искал их, но я не нашел решения по моему вопросу. Я смущен логикой в ​​следующей программе.

Если я запустил программу ниже, она выдаст правильный результат, но я не понял логики.

  • Я не понял логику в следующей строке: result = fact (n-1) * n;
  • Насколько я знаю, если мы передадим значение n = 4, как показано в приведенной ниже программе,
  • Тогда 3 * 4 сохраняется в результате, т. Е. 12.
  • Опять же, факт (n-1) называется. Тогда n становится 3.
  • Затем 2 * 3 сохраняется в результате, заменяющем предыдущие 12.
  • Я думаю, вы поняли, где я застрял / запутался.

  • Спасибо.

class Calculation { int fact(int n) { int result; if(n==1) return 1; result = fact(n-1) * n; return result; } } public class Factorial { public static void main(String args[]) { Calculation obj_one = new Calculation(); int a = obj_one.fact(4); System.out.println("The factorial of the number is : " + a); } } 

result является локальная переменная метода fact . Поэтому каждый раз, когда вызывается метод факта, результат сохраняется в другой переменной, чем предыдущий вызов факта.

Поэтому, когда факт вызывается с аргументом 3 в качестве аргумента, вы можете себе представить, что его результат

  result3 = fact(2) * 3 result3 = result2 * 3 result3 = 1 * 2 * 3 

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

Возьмем 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 . Это как колода карт, где каждая карта помещена над другой – и каждая карта может считаться функцией. Итак, передавая метод:

Уровень стека 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 

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

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

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

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

Вот расчет 3! подробно:

введите описание изображения здесь

Источник: RECURSION (Java, C ++) | Алгоритмы и структуры данных

Я полагаю, что ваше замешательство связано с тем фактом, что вы считаете, что есть только одна переменная result , тогда как на самом деле есть переменная result для каждого вызова функции. Поэтому старые результаты не заменяются, а возвращаются.

РАЗРАБОТАТЬ:

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

Предположим, что вызов fact(2) :

 int result; if ( n == 1 ) // false, go to next statement result = fact(1) * 2; // calls fact(1): | |fact(1) | int result; //different variable | if ( n == 1 ) // true | return 1; // this will return 1, ie call to fact(1) is 1 result = 1 * 2; // because fact(1) = 1 return 2; 

Надеюсь, теперь все ясно.

Случается, что сам рекурсивный вызов приводит к дальнейшему рекурсивному поведению. Если вы должны были написать это, вы получите:

  fact(4) fact(3) * 4; (fact(2) * 3) * 4; ((fact(1) * 2) * 3) * 4; ((1 * 2) * 3) * 4; 
 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); } } 

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

Хотя это и старо, все еще продолжает хорошо расти в Google. Поэтому я решил, что упомянул об этом. Никто не упоминается, чтобы проверить, когда x = 0 .

0! и 1! оба = 1.

Это не проверяется с помощью предыдущих ответов и вызывает переполнение стека, если был запущен факт (0). Во всяком случае, простое исправление:

 public static int fact(int x){ if (x==1 | x==0) return 1; return fact(x-1) * x; }// fact 

Рекурсивное решение с использованием тернарных операторов.

 public static int fac(int n) { return (n < 1) ? 1 : n*fac(n-1); } 

На мой взгляд, и если вы считаете, что кто-то знает знание java уровня начинающего уровня, я бы предположил, что n == 1 будет изменен на n <= 1 или (n == 0) || (n == 1) потому что факториал 0 равен 1.

Правильный вариант:

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

Это вернет 1 для факториала 0. Поверьте мне. Я усвоил этот трудный путь. Просто для того, чтобы не поддерживать условие для 0, не удалось снять интервью.

Чтобы понять это, вы должны объявить метод самым простым способом, и мартинас прибил его 6 мая:

 int fact(int n) { if(n==0) return 1; else return n * fact(n-1); } 

прочитайте приведенную выше реализацию, и вы поймете.

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

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

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

не создавайте еще одну переменную

результат

просто

return fact (n-1) * n;

 class Calculation { int fact(int n) { int result; if(n==1) return 1; return fact(n-1) * n; } } 
 import java.util.Scanner; public class Factorial { public static void main(String[] args) { Scanner keyboard = new Scanner(System.in); int n; System.out.println("Enter number: "); n = keyboard.nextInt(); int number = calculatefactorial(n); System.out.println("Factorial: " +number); } public static int calculatefactorial(int n){ int factorialnumbers=1; while(n>0){ factorialnumbers=(int)(factorialnumbers*n--); } return factorialnumbers; } } в import java.util.Scanner; public class Factorial { public static void main(String[] args) { Scanner keyboard = new Scanner(System.in); int n; System.out.println("Enter number: "); n = keyboard.nextInt(); int number = calculatefactorial(n); System.out.println("Factorial: " +number); } public static int calculatefactorial(int n){ int factorialnumbers=1; while(n>0){ factorialnumbers=(int)(factorialnumbers*n--); } return factorialnumbers; } } , import java.util.Scanner; public class Factorial { public static void main(String[] args) { Scanner keyboard = new Scanner(System.in); int n; System.out.println("Enter number: "); n = keyboard.nextInt(); int number = calculatefactorial(n); System.out.println("Factorial: " +number); } public static int calculatefactorial(int n){ int factorialnumbers=1; while(n>0){ factorialnumbers=(int)(factorialnumbers*n--); } return factorialnumbers; } } 
 public class Factorial2 { public static long factorial(long x) { if (x < 0) throw new IllegalArgumentException("x must be >= 0"); if (x <= 1) return 1; // Stop recursing here else return x * factorial(x-1); // Recurse by calling ourselves } } 
 public class Factorial { public static void main(String[] args) { int n = 7; int result = 1; for (int i = 1; i <= n; i++) { result = result * i; } System.out.println("The factorial of 7 is " + result); } } 

Ну вот логика найти факториал числа, используя рекурсию,

 static int factorialFunction(int n) { int result; if(n == 1) { return 1; } // here we are calling the recursion function result = factorialFunction(n - 1) * n; return result; } 

Тем временем вы можете ссылаться на этот ресурс, чтобы найти примеры по факториалу числа, используя рекурсию.

  • Поиск файла в каталогах рекурсивно
  • Поиск максимального значения в массиве с использованием рекурсии
  • Получить список подкаталогов в VBA
  • Рекурсия или итерация?
  • Рекурсивный вызов ConcurrentHashMap.computeIfAbsent () никогда не завершается. Ошибка или «функция»?
  • Реальные примеры рекурсии
  • Рекурсия хвоста в C ++
  • Я получил «приложение схемы не процедуру» в последнем рекурсивном вызове функции
  • Что такое нерекурсивное решение для последовательности, подобной Фибоначчи, в Java?
  • Почему функции в Ocaml / F # не рекурсивны по умолчанию?
  • рекурсивный вариационный шаблон для распечатки содержимого пакета параметров
  • Давайте будем гением компьютера.