Récursion Java : concepts et utilisation

1. Le concept de récursion

1.

La récursion est : le processus d'appel d'une méthode par elle-même.

Il y a deux conditions préalables à l'utilisation de la récursivité :

1 Il existe une condition d'approche et de terminaison.

2. Appelez-vous.

Comment implémenter la récursivité ?

Le moyen le plus important est le suivant : pour implémenter la récursivité, vous devez dériver une formule de récursion.

La façon de penser la récursion : penser latéralement et penser selon la formule récursive.

Exécution du code : exécution verticale.

2. Explication de la récursion

Regardez d'abord le code suivant :

public class TestDemo {
    public static void func(){
        
        func();   //自己调用自己本身
    }
 
 
    public static void main(String[] args) {
        func();
 
    }
}

Le code ci-dessus est une simple récursion.

Regardons à nouveau les résultats d'exécution de ce code,

Explication de l'image :

Pour la récursivité dans l'image ci-dessus, il n'y a aucune condition qui a tendance à se terminer, donc cette fonction se répétera sans fin. Chaque fois que vous récurez, la mémoire doit être allouée sur la pile. Si vous continuez à allouer de la mémoire sur la pile, la pile finira par déborder.

Vétérans, n'oubliez pas : une fois qu'il y a un problème avec la récursivité que vous écrivez, si la limite n'est pas trouvée correctement, elle signalera certainement une erreur

Si cette erreur est signalée, ce doit être votre résiliation. la condition est fausse, ou le fait de ne pas écrire une condition de terminaison vous amène à aller trop loin dans le processus récursif et éventuellement la pile déborde.

Si nous voulons que le code ci-dessus soit correct, nous devons y ajouter une condition de résiliation.

Le code correct est le suivant :

public class TestDemo {
    public static void func(int n){
        if(n == 1) return;
        func(n -1);
    }
 
 
    public static void main(String[] args) {
        func(3);
 
    }
}

Ce qui suit vous donnera une compréhension plus approfondie de la récursion à travers des exemples simples

2. Utilisation de la récursion

Exemple : Trouver la factorielle de n de manière récursive Analyse de dessin :

Code d'implémentation :

public class TestDemo {
    public static int fac(int n){
        if(n == 1) {
            return 1;
        }
        int tmp = n * fac(n - 1);
        return tmp;
    }
    public static void main(String[] args) {
        System.out.println(fac(5));
 
    }
}

Explication du dessin de code :

Exemple : Trouver la somme de n

Analyse du dessin :

Code d'implémentation :

第一种写法：
public class TestDemo {
    public static int sumAdd(int n){
        if(n == 1) {
            return 1;
        }
        int tmp = n + sumAdd(n - 1);
        return tmp;
    }
    public static void main(String[] args) {
        System.out.println(sumAdd(3));
 
    }
}
 
第二种写法：
public class TestDemo {
    public static int sumAdd(int n){
        if(n == 1) {
            return 1;
        }
       
        return n + sumAdd(n -1);
    }
    public static void main(String[] args) {
        System.out.println(sumAdd(3));
 
    }
}

Exemple : L'implémentation récursive imprime chaque chiffre dans l'ordre

Dessin Analyse：

Code d'implémentation :

public class TestDemo {
 
    public static void print(int n){
        if(n < 10){
            System.out.print(n+" ");
        }else{
            print(n/10);
            System.out.print(n%10+" ");
        }
    }
    public static void main(String[] args) {
        print(1234);
 
 
    }
}

Exemple : Écrivez une méthode récursive, saisissez un entier non négatif et renvoyez la somme des nombres qui la composent. Par exemple : si vous entrez 1729, il devrait renvoyer 1+7+2+9

Code d'implémentation :

public class TestDemo {
 
 
    public static int sumEveryone(int n){
        if(n < 10){
           return n;
        }else{
            return n%10 + sumEveryone(n/10);
        }
    }
 
    public static void main(String[] args) {
        System.out.println(sumEveryone(7910));
 
    }
 
}

Exemple de question : Trouver le nième nombre de Fibonacci

Analyse de dessin :

Code d'implémentation :

第一种方法：递归
public class TestDemo {
    public static int fib(int n){
        if(n == 1 || n == 2){
            return 1;
        }else{
            return fib(n-2)+fib(n-1);
        }
    }
    public static void main(String[] args) {
        System.out.println(fib(5));
 
    }
 
 
 
第二种方法：叫做循环(迭代）实现
    public static int fib2(int n){
        if(n == 1 || n==2){
            return 1;
        }
            int f1 = 1;
            int f2 = 1;
            int f3 = 0;
            for (int i = 3; i < n; i++) {
                f3 = f1+f2;
                f1 = f2;
                f2 = f3;
            }
            return f3;
 
    }
    public static void main(String[] args) {
        System.out.println(fib2(45));
 
    }

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!