J'ai décidé de mettre en place un programme très simple de manière récursive, de voir à quel point Java gère la récursion * et est arrivé un peu courte. C'est ce que j'ai fini par écrire: et cela fonctionne bien, mais comme il est un peu moche, je me suis demandé s'il y avait une meilleure façon. Si quelqu'un a des pensées / alternatives / sucre syntaxique à partager, cela serait très apprécié! P.S. Si vous dites "Utilisez LISP", vous ne gagnez rien (mais respect). Je veux savoir si cela peut être fait pour être jadis dans Java . * et comment bien i manipulez la récursion >
11 Réponses :
Vous pouvez transmettre l'index actuel sous forme de paramètre plutôt que de copier presque toute la matrice à chaque fois ou que vous pourriez utiliser une approche de division et de conquérir.
Voici comment je pourrais faire de la méthode récursive plus agréable:
private static int recursive(int[] ints, int largest) {
return recursive(ints, largest, 0);
}
Jooi, y a-t-il une différence entre Math.Max et un opérateur ternaire avec un plus grand que?
Oui, je trouve que l'utilisation de max () est plus facile à lire que d'utiliser l'opérateur conditionnel Java dans le même but. S'il y a une différence de performance, vous devrez le mesurer pour votre environnement spécifique.
Avec max (), vous n'avez pas à vous répéter vous-même.
public static int max(int[] numbers) {
int size = numbers.length;
return max(numbers, size-1, numbers[size-1]);
}
public static int max(int[] numbers, int index, int largest) {
largest = Math.max(largest, numbers[index]);
return index > 0 ? max(numbers, index-1, largest) : largest;
}
2 améliorations:
pas besoin de donner le maximum actuel p>
private static int recursive(int[] ints, int offset) {
if (ints.length - 1 == offset) {
return ints[offset];
} else {
return Math.max(ints[offset], recursive(ints, offset + 1));
}
}
En fait, je préférais celui-ci parce que son utilisation de récursivité est plus légérable que la réponse gagnante, mais cela ne fait pas certaines choses que le gagnant fait. Merci quand même :)
Tel que? La seule différence à mes yeux est la manipulation d'un tableau vide qui jette une exception ici (bon, il n'y a pas de maximum, donc aucune bonne réponse) vs retourne une valeur arbitraire (FALSE) dans la réponse gagnante.
Votre code récursif utilise system.arraycopy , mais votre code itératif ne fait pas cela, votre microbenchmark ne sera pas exacte. Comme d'autres les ont mentionnés, vous pouvez nettoyer ce code en utilisant math.min et à l'aide d'un index de tableau au lieu de l'approche de type file d'attente que vous aviez.
... pour voir à quel point Java traite la récursion
La réponse simple est que Java ne gère pas bien la récursion. Plus précisément, Sun Java Compilers et Hotspot JVMS ne mettent pas en œuvre l'optimisation de la récursion de l'appel de la queue, de sorte que les algorithmes intensives de récursives peuvent facilement consommer beaucoup d'espace de pile.
Cependant, j'ai vu des articles qui disent que les JVMS d'IBM faire soutiennent cette optimisation. Et j'ai vu un email de certains non-soleil qui a dit qu'il l'a ajouté comme une extension expérimentale d'hotspot en tant que projet de thèse.
Voici une légère variation montrant comment les listes liées sont souvent un peu plus agréables pour la récursivité, où "plus sien" signifie "moins de paramètres dans la signature de méthode"
public class Maximum
{
/**
* Just adapted the iterative approach of finding maximum and formed a recursive function
*/
public static int max(int[] arr,int n,int m)
{
if(m < arr[n])
{
m = arr[n];
return max(arr,n - 1,m);
}
return m;
}
public static void main(String[] args)
{
int[] arr = {1,2,3,4,5,10,203,2,244,245,1000,55000,2223};
int max1 = max(arr,arr.length-1,arr[0]);
System.out.println("Max: "+ max1);
}
}
Bienvenue dans le débordement de la pile! Souhaitez-vous envisager d'ajouter un récit pour expliquer pourquoi ce code fonctionne et ce qui en fait une réponse à la question? Cela serait très utile pour la personne qui pose la question et quiconque qui vient.
Je dispose en fait d'une classe pré-formée que je configurie pour trouver le plus grand nombre d'entiers de tout ensemble de valeurs. Vous pouvez mettre cette classe dans votre projet et simplement l'utiliser dans n'importe quelle classe, comme:
public class figures {
public static int getLargest(int...f) {
int[] score = new int[f.length];
int largest=0;
for(int x=0;x<f.length;x++) {
for(int z=0;z<f.length;z++) {
if(f[x]>=f[z]) {
score[x]++;
}else if(f[x]<f[z]) {
}else {
continue;
}
if(z>=f.length) {
z=0;
break;
}
}
}
for(int fg=0;fg<f.length;fg++) {
if(score[fg]==f.length) {
largest = f[fg];
}
}
return largest;
}
}
Ce qui suit est un exemple de code donné par mon instructeur Java, professeur Penn Wu, dans l'une de ses conférences. J'espère que cela aide.
Bienvenue pour! Veuillez envisager d'éditer votre question pour inclure des explications détaillées sur les raisons et la manière dont ce code répond à la question. De plus, vous voudrez peut-être recevoir la permission avant de poster le code d'un professeur ou son nom associé audit code, comme une courtoisie commune.
Voici mon alternative
public class recursion
{
public static int max( int[] n, int index )
{
if(index == n.length-1) // If it's simple, solve it immediately:
return n[index]; // when there's only one number, return it
if(max(n, index+1) > n [index]) // is one number bigger than n?
return max(n, index+1); // return the rest, which contains that bigger number
return n[index]; // if not, return n which must be the biggest number then
}
public static void main(String[] args)
{
int[] n = {100, 3, 5, 1, 2, 10, 2, 15, -1, 20, -1203}; // just some numbers for testing
System.out.println(max(n,0));
}
}
La récursion ne sera pas aussi simple ou efficace en Java comme itération, sauf cas très rares.
Ouais, mais si quelqu'un va être bien préparé pour la complexité spatiale de la récursivité, c'est un développeur Java :)
Dans n'importe quelle langue, vous devrez toujours copier la matrice ou passer des indices dans ce tableau. Si vous voulez dire "LISP à l'aide d'une liste liée", alors sûr, c'est plus agréable que "Java à l'aide d'un tableau", mais je pense que "x à l'aide d'une liste liée" est plus agréable que "y à l'aide d'un tableau" pour tous les X et Y. ( Des tableaux déplacés dans une poignée de LISP commune Un peu de la comptabilité pour vous, mais je ne pense pas qu'ils rendent vraiment ce cas beaucoup plus simple.)