Factorielle utilisant la récursivité en Java

Vous devez d'abord comprendre comment fonctionne la factorielle.

Permet de prendre 4! à titre d'exemple.

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

Simulons le code en utilisant l'exemple ci-dessus:

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

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

, Dans la plupart des langages de programmation, nous avons ce que nous appelons function stack. C'est comme un jeu de cartes, où chaque carte est placée au-dessus de l'autre--et chaque carte peut être considérée comme une fonction, en transmettant la méthode fact:

Niveau de pile 1: fact(4) // n = 4 and is not equal to 1. So we call fact(n-1)*n

Niveau de pile 2: fact(3)

Niveau de pile 3: fact(2)

Niveau de la Pile 4: fact(1) // maintenant, n = 1. nous retournons donc 1 de cette fonction.

Renvoie des valeurs...

Niveau de pile 3: 2 * fact(1) = 2 * 1 = 2

Niveau de pile 2: 3 * fact(2) = 3 * 2 = 6

Niveau de pile 1: 4 * fact(3) = 4 * 6 = 24

Donc on en a 24.

Prenez note de ces lignes:

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

, Ou simplement:

return fact(n-1) * n;

Cela appelle la fonction elle-même. En utilisant 4 comme exemple,

En séquence selon les piles de fonctions..

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

Substitution résultat...

return 1 * 2 * 3 * 4 = return 24

J'espère que vous comprendrez.

Voici encore une autre explication du fonctionnement du calcul factoriel utilisant la récursivité.

Modifions légèrement le code source:

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

Voici le calcul de 3!{[3] } en détails:

Source: RÉCURSIVITÉ (Java, C++ | / Algorithmes et structures de données

Votre confusion, je crois, vient du fait que vous pensez qu'il n'y a qu'une seule variable result, alors qu'en fait il y a une variable result pour chaque appel de fonction. Par conséquent, les anciens résultats ne sont pas remplacés, mais renvoyés.

POUR ÉLABORER:

int fact(int n)
{
    int result;

   if(n==1)
     return 1;

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

Supposons un appel à 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, i.e. call to fact(1) is 1
result = 1 * 2; // because fact(1) = 1
return 2;

J'espère que c'est plus clair maintenant.

Ce qui se passe, c'est que l'appel récursif lui-même entraîne un comportement récursif supplémentaire. Si vous deviez l'écrire, vous obtenez:

 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);
    }
}

Le point clé qui vous manque ici est que la variable "result" est une variable de pile, et en tant que telle, elle n'est pas "remplacée". Pour élaborer, chaque fois que fact est appelé, une NOUVELLE variable appelée "result" est créée en interne dans l'interpréteur et liée à cette invocation des méthodes. Ceci est en contraste avec les champs d'objet qui sont liés à l'instance de l'objet et non à un appel de méthode spécifique

Bien que ce soit vieux, il continue à venir assez bien dans Google. Alors j'ai pensé que je voudrais mentionner. Personne n'a mentionné pour vérifier quand x = 0.

0! et 1! les deux = 1.

Ceci n'est pas vérifié avec les réponses précédentes, et provoquerait un débordement de pile, si fact(0) était exécuté. Quoi qu'il en soit simple fix:

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

Une solution récursive utilisant des opérateurs ternaires.

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

À mon avis, et cela étant l'opinion de quelqu'un ayant une connaissance de niveau débutant de java, je suggérerais que le n == 1 soit changé en n

Le bon est:

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

Cela renverrait 1 pour la factorielle 0. Faire crois moi . J'ai appris cela à la dure. Juste pour ne pas garder la condition pour 0 n'a pas pu effacer une interview.

Pour le comprendre, vous devez déclarer la méthode de la manière la plus simple possible et martynas l'a clouée le 6 mai:

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

Lisez l'implémentation ci-dessus et vous comprendrez.

À mon humble avis, la clé pour comprendre les actions liées à la récursivité est:

1. Tout d'abord, nous plongeons dans la pile récursivement, et à chaque appel nous modifier en quelque sorte une valeur (par exemple n-1 dans func(n-1);) qui détermine si le la récursivité devrait aller de plus en plus loin.
2. Une fois La récursionStopCondition est remplie (par exemple n == 0), les récursions s'arrêtent, et les méthodes font le travail réel et renvoient des valeurs à la méthode de l'appelant dans piles supérieures, bouillonnant ainsi vers le haut de la pile.
3. C'est important pour attraper la valeur renvoyée par une pile plus profonde, en quelque sorte modifiez-le (en multipliant par n dans votre cas), puis renvoyez ceci valeur modifiée vers le haut de la pile. L'erreur commune est que l' la valeur du cadre de pile le plus profond est renvoyée directement vers le haut de la pile, de sorte que toutes les invocations de méthode soient ignorées.

Sûrement, les méthodes peuvent faire un travail utile avant de plonger dans la récursivité (du haut vers le bas de la pile), ou sur le chemin du retour.

Ne créez pas une variable de plus

Résultat

Simplement

Retourner le fait (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;
    }
}

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);
}
}

Eh bien, voici la logique pour trouver la factorielle d'un nombre en utilisant la récursivité,

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;
}

Pendant ce temps, vous pouvez vous référer à cette ressource pour trouver des exemples sur la factorielle d'un nombre en utilisant la récursivité.