1. Les fonctions récursives, en termes simples, signifient que la fonction elle-même s'appelle...
Tel que : n!=n(n-1) !
Vous définissez la fonction f(n)=nf(n-1)
Et f(n-1) est fonction de cette définition. . C'est une récursion
2. Pourquoi utiliser la récursivité : le but de la récursivité est de simplifier la conception du programme et de rendre le programme plus facile à lire.
3. Inconvénients de la récursivité : Bien que les fonctions non récursives soient très efficaces, elles sont difficiles à programmer et ont une mauvaise lisibilité. L’inconvénient des fonctions récursives est qu’elles augmentent la surcharge du système, c’est-à-dire qu’à chaque fois qu’elles sont récursives, la mémoire de la pile prend plus d’espace.
4. Conditions de récursivité : il doit y avoir une instruction pour terminer la tâche et les exigences de récursivité doivent être remplies (réduire plutôt que diverger)
5. Avancement récursif :
1. Utilisez la récursivité pour calculer la factorielle de n :
Analyse : n!=n*(n-1)*(n-2)...*1
public int dReturn(int n){ if(n==1){ return 1; else{ return n*dReturn(n-1 } })2. Utilisez la fonction récursive pour calculer l'accumulation de 1 à n : 1+2+3+4+..+n
public int dReturn(int n){ if(n==1){ return 1; else{ return n+dReturn(n-1 } }) 3. Il est nécessaire de générer une séquence : 1,1,2,3,5,8,11... (chaque nombre est la somme des deux nombres précédents, et une fonction récursive est requise)
Utilisez la récursion Java pour représenter une fonction : F(n)=F(n-1)+F(n-2);F(0)=1;F(1)=1;
Analyse : X1=1 ; X2=1 ; X3=X1+X2 ;
public int F(int n){ if(n==1){ return 1; }else if(n==2){ return 1 }else{ return F(n-1)+F(n-2); } }4.Java utilise une méthode récursive pour imprimer inversément chaque élément d'un tableau d'entiers
public static void printAll(int index,int[] arr){ System.out.println(arr[index]); if(index > 0){ printAll(--index,arr } } public static void main(String); [] args){ int[] arr={1,2,3,4,5}; printAll(arr.lenth-1,arr });5. Solution de programmation : Si une génisse donne naissance à une vache chaque année à partir de la quatrième année après la naissance, combien y a-t-il de vaches la nième année ?
public static int bétail(int n){ if(n<=0){ return 0; }else if(n<=3){ return 1 }else{ return bétail(n-1)+cattle(n-3) ; } } public static void main(String[] args){ int n=10; System.out.println(n+"Il y aura un total de "+cattle(n)+"vaches" après l'année);Quels sont les concepts de récursivité, de récursivité linéaire et de récursivité de queue ?
Appel de fonctions récursives en Java - trouver la factorielle d'un nombre
Le débordement n'est pas pris en compte : généralement seule la factorielle de 69 peut être calculée...
Remarque : la factorielle de 0 est 0 ! =1
La représentation factorielle de tout nombre naturel n supérieur à 1 :
n!=1×2×3×……×n
Ou n!=n×(n-1)!
La recherche de la factorielle de 0 fera apparaître une calculatrice en ligne, ce qui est très utile ! !
package test;import java.util.Scanner;public class DiGui {public static void main(String[] args) {// TODO Méthode générée automatiquement stubSystem.out.println("Entrez un entier :");Scanner scan = new Scanner(System.in);int x = scan.nextInt();int résultat = digui(x);System.out.println(result);}//Fonction récursive public static int digui(int x){if(x<=0){return 1;}else{return x*digui(x-1 );}}}Récursion : un processus ou une fonction a une méthode pour s'appeler directement ou indirectement dans sa définition ou sa description. Il transforme généralement un problème vaste et complexe en un problème plus petit similaire au problème d'origine à résoudre. Ce cas illustre clairement comment la récursivité peut transformer un problème complexe en un problème plus petit à résoudre. Ce qui suit est un petit exemple pour illustrer le principe de récursivité.
/*** @fileName Test.java* @description ??????????* @date 2012-11-25* @time 17:30* @author wst*/public class Test { static int multiplier( int n) { int factoriel ; // ?? if ((n == 1) || (n == 0)) { factoriel = n } else { factoriel = n * multiplier (n - 1) ; ; } public static void main(String[] args) { System.out.println(multiply(5) }} Lorsqu'une fonction est appelée, un espace pour ses variables est créé sur la pile d'exécution. Les variables de la fonction précédemment appelée restent sur la pile, mais elles sont masquées par les variables de la nouvelle fonction et ne sont donc pas accessibles.
La fonction dans le programme a deux variables : le paramètre n et la variable locale factorielle. Les diagrammes suivants montrent l'état de la pile, avec les variables actuellement accessibles en haut. Toutes les autres variables appelées sont ombrées en gris pour indiquer qu'elles ne sont pas accessibles par la fonction en cours d'exécution.
Supposons que nous appelions la fonction récursive avec la valeur 5. Le contenu de la pile est le suivant, le haut de la pile étant en bas :
n multiplier(n) factorielle 5 multiplier(5) 5*multiply(4) //Premier appel 4 multiplier(4) 4*multiply(3) //Deuxième appel 3 multiplier(3) 3*multiply(2 ) //Le troisième appel 2 multiplier(2) 2*multiply(1) //Le quatrième appel 1 multiplier(1) 1 //Le cinquième appel
À partir des informations ci-dessus, il est facile de voir comment la récursivité minimise progressivement un problème pour le résoudre. À partir de l'appel de méthode, les résultats factoriels seront placés sur la pile jusqu'à la fin de l'appel de méthode, et enfin les résultats seront renvoyés un par un. du haut de la pile. Après substitution une à une, le résultat est le suivant :
n=1 1 renvoie 1 vers le haut
n=2 2*multiply(1) renvoie 2*1=2 vers le haut
n=3 3*multiply(2) renvoie 3*(2*1)=6 vers le haut
n=4 4*multiply(3) renvoie 4*(3*(2*1))=24 vers le haut
n=5 5*multiply(4) renvoie vers le haut 5*(4*(3*(2*1)))=120
Remarque : Parce que multiplier(1) ou multiplier(0) renvoie une valeur de 1
Il y a donc 2*multiply(1)=2*1=2
Et parce que multiplie(2) répond à la condition de récursion, il peut être transformé en 2*multiply(1) après récursion.
Il y a donc 3*multiply(2)=3*(2*multiply(1))=3*(2*1)=6
Parce que multiplier(3) peut être réduit à 3*multiply(2) après récursion
Donc multiplier(4)=4*multiplier(3)=4*(3*multiplier(2))=4*(3*(2*1))=24
Par analogie, multiplier(5)=5*multiplier(4)
Il peut être réduit à 5*(4*multiply(3))=5*(4*3*(multiply(2)))=5*(4*(3*(2*1)))=120
Jetons un coup d'œil aux informations du bytecode :
public class Test extends java.lang.Object{ public Test(); Code : 0 : aload_0 1 : invokespecial #1 ; //Méthode java/lang/Object."<init>":()V 4 : return static int multiplier (int); Code : 0 : iload_0 1 : iconst_1 //Pousser la constante de type int 1 sur la pile 2 : if_icmpeq 9 //Comparez deux valeurs de type int. Si elles sont égales, passez à la position 9. C'est la fonction de court-circuit de ||5 : iload_0 // Ceci est exécuté lorsque la première condition n'est pas remplie, à partir de la variable locale 0 Load une valeur de type int (poussez la valeur de n sur la pile) 6 : ifne 14 //Comparez, s'il n'est pas égal à 0, passez à la position 14. Remarque : Puisque la valeur par défaut ici est comparée à 0, il n'est pas nécessaire de la modifier la constante à 0 Appuyez sur 9 : iload_0 // S'il n'y a pas de saut à ifne, chargez la valeur de type int à partir de la variable locale 0 (insérez la valeur de n sur la pile) 10 : istore_1 // Stockez la valeur de type int dans la variable locale 1 (insérez la valeur en haut de la pile) Autrement dit, la valeur de la variable locale 0 est poussée sur la pile puis stockée dans la variable locale 1) 11 : goto 23 //Sauter sans condition à la position 23 14 : iload_0 //Comparaison en position 6, si elle n'est pas égale à 0, exécutez cette instruction et chargez la valeur de type int depuis la variable locale 0 (poussez la valeur de n sur la pile) 15 : iload_0 //Chargez la valeur de type int depuis local variable 0 (poussez la valeur de n sur la pile) Poussez la valeur de n sur la pile) 16 : iconst_1 //Poussez la constante de type int 1 sur la pile, la constante 1 est 1 de n-1 dans le code 17 : isub //Effectuer l'opération de soustraction, n-1 18 : invocatestatic #2; multiplier:(I)I, appeler la méthode multiplier 21 : imul //Effectuer une opération de multiplication, n * multiplier(n - 1) 22 : istore_1 //Stocker la valeur de type int dans la variable locale 1, factorielle=... 23 : iload_1 / /Charger la valeur de type int à partir de la variable locale 1 (pousser le résultat de la factorielle sur la pile) 24 : ireturn //La méthode renvoie public static void main(java.lang.String[]); #3 ; //Champ java/lang/System.out:Ljava/io/PrintStream; 3 : iconst_5 4 : invoquerstatique #2 ; //Méthode multiplier :(I)I 7 : invoquervirtual #4 ; /PrintStream.println:(I)V 10 : retour }