3
votes

Problème de récursivité - cette solution est-elle correcte, et y en a-t-il une plus simple?

Je suis nouveau dans la récursivité et j'ai trouvé le problème Java suivant:
Écrivez une fonction qui obtient un entier n et affiche les nombres 1!, 2!, 3!, ..., n !.
Voici ce que j'ai fait et j'aimerais savoir si c'est la solution la plus simple (je ne suis pas sûr car j'ai utilisé la boucle "for" pour le faire).

public static void Print(int n) {
  if (n == 0) {
    System.out.print("1");
  } else {
    int temp = 1;
    for (int i = 1; i <= n, i++) {
      temp = temp * i;
    }
    Print(n-1);
    System.out.print(temp);
  }
}

Au fait, l'exercice précédent consistait à écrire une fonction qui obtient un entier n et renvoie n !, en utilisant la récursivité. Pensez-vous que je dois l'utiliser ici et l'imprimer au lieu de calculer la température (n!) Et de l'imprimer? Merci!


6 commentaires

Vous avez une erreur de syntaxe dans le code publié


@ButiriDan Merci, je l'ai réparé


Pour cette fonction, vous voudrez plutôt utiliser un long. Les factorielles provoquent un débordement fou rapidement car la croissance est si élevée.


ce n'est pas vraiment une bonne façon de le résoudre de manière récursive


Cela n'a pas beaucoup de sens d'utiliser à la fois la récursivité et une boucle for. Vous pouvez résoudre le problème en utilisant l'un ou l'autre.


Alors, que dois-je faire à la place? Notez que j'ai très peu d'expérience et de connaissances donc je ne connais que les choses de base


6 Réponses :


1
votes

Sans récursivité

3628800

La récursion est votre boucle

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

public static long print(long n) {
    if (n == 0) {
        return 1;
    }
    return n * print(n - 1);
}

Production

int temp = 1;
for (int i = 1; i <= 10; ++i) {
    temp *= i;
}
System.out.println(temp);


2 commentaires

La question n'est pas claire, mais je crois que le but est d'imprimer n factoriel , pas littéralement d'imprimer n!


C'est maintenant ainsi que j'ai compris la question, je pense qu'il faut imprimer la valeur et non k!



1
votes

Ce que vous avez écrit fonctionne, mais vous recalculez un tas de choses, et vous utilisez toujours une boucle for alors que vous pourriez faire tout cela de manière récursive et avec moins de code.

En supposant que vous êtes bloqué en utilisant la fonction Print(int n) , vous pouvez écrire moins de code et ne calculer chaque factorielle qu'une seule fois en recursant vers le haut à partir de 1 et en emportant les calculs avec elle:

public static void Print(int n) {
    PrintHelper(1, n, 1);
}

private static void PrintHelper(int i, int n, long factorial) {
    if (i > n)
        return;

    factorial *= i;
    System.out.println(factorial);
    PrintHelper(i + 1, n, factorial);
}

Ceci est plus facile à lire, plus facile à raisonner et évite de refaire sans cesse les mêmes calculs.

Dans l'exemple que j'ai posté ci-dessus, je fais n multiplications. Dans votre exemple, vous effectuez environ n^2 / 2 2/2 multiplications puisque vous répétez encore et encore chaque nombre (ex: 1 * 2 * 3 * ... * 50, puis 1 * 2 * 3 * ... * 49, puis 1 * 2 * 3 * ... * 48, ... etc).

Le code que j'ai écrit omet la vérification des erreurs pour la brièveté de la démonstration, car vous pouvez facilement y ajouter des vérifications de cohérence d'entrée.


0 commentaires

1
votes

Voici une solution récursive simple:

  public static long factorial(long n) {
    if(n == 0 || n == 1) {
      System.out.print(1 + " ");
      return 1;
    }

    long result = n * factorial(n - 1);
    System.out.print(result + " ");
    return result;
  }


3 commentaires

Merci mais je n'ai pas encore appris ce qui est "long", je ne fais que commencer et l'exercice ne devrait utiliser que des choses basiques


long est un type numérique qui stocke plus de bits que int avant de déborder. Ils sont totalement interchangeables dans ce cas, à condition que n! <2 147 483 647


long est juste un type de données primitif comme int qui peut stocker des nombres plus grands. L'utilisation d'un int pour les factorielles peut provoquer des débordements d'entiers très rapidement. Voir docs.oracle.com/javase/tutorial/java/nutsandbolts/...



1
votes

Un one-liner ressemblera à:

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

L' opérateur ternaire replie l'instruction if. Ensuite, en utilisant la récursivité, chaque appel de fonction devient un facteur dans la fonction factorielle, jusqu'à ce que le cas de base ( n <= 2 ) soit atteint:

4 * factorielle (3)

4 * 3 * factorielle (2)

4 * 3 * 2


0 commentaires

0
votes

En utilisant la récursivité pour obtenir la factorielle d'un nombre (exercice précédent), cette méthode ressemblera à quelque chose comme

void factorials(long n) {
    long factorial = 1;
    System.out.println(factorial); // 0!
    for (long i = 1; i <= n; i++) {
        factorial *= i;
        System.out.println(factorial);
    }
}

Compte tenu de cela, il est préférable de ne pas utiliser de récursivité et d'utiliser simplement une boucle pour obtenir la factorielle d'un nombre, comme ceci:

long[] factorials(long n) {
    long[] factorials = new long[n+1];
    long factorial = 1;
    for (long i = 1; i <= n; i++) {
        factorial *= i;
        factorials[n] = factorial;
    }
    factorials[0] = 1;
    return factorials;
}

si vous voulez tous les numéros de la série

long factorial(long n) {
    long factorial = 1;
    for (long i = 1; i <= n; i++) {
        factorial *= i;
    }
    return factorial;
}

Si vous avez seulement besoin de les imprimer, la méthode devient

long factorial(long n) {
    if (n > 0) {
        return n*factorial(n - 1);
    }
    return 1;
}


0 commentaires

0
votes

Cela ajoute une impression d'une manière qui ne rend pas l'expression récursive plus difficile à lire.

public class Fact {

    public static void main(String... args) {
        fact(5L);
        System.out.println();
    }

    static long fact(long n) {
        return print(
            n == 0 || n == 1 ? 1 : n * fact(n - 1));
    }

    static long print(long i) {
        System.out.print(Long.toString(i));
        return i;
    }
}


0 commentaires