Java Recursion: Konsep dan Penggunaan

1 Konsep rekursi

1.

Rekursi ialah: proses memanggil kaedah dengan sendirinya.

Terdapat dua prasyarat untuk menggunakan rekursi:

1. Terdapat pendekatan dan syarat penamatan.

2.

Bagaimana untuk melaksanakan rekursi?

Cara yang paling penting ialah: untuk mencapai rekursi, anda perlu memperoleh formula rekursi.

Cara berfikir tentang rekursif: fikir secara sisi, fikir mengikut formula rekursif.

Pelaksanaan kod: pelaksanaan menegak.

2. Penjelasan rekursi

Pertama lihat kod berikut:

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

Kod di atas ialah rekursi mudah.

Mari kita lihat hasil larian kod ini sekali lagi

Penjelasan lukisan:

Untuk rekursi dalam gambar di atas. , tiada syarat A yang cenderung untuk ditamatkan, jadi fungsi ini akan berulang tanpa henti. Setiap kali anda mengulangi, memori mesti diperuntukkan pada tindanan Jika anda terus memperuntukkan memori pada tindanan, tindanan akhirnya akan melimpah.

Veteran, sila ingat: Apabila terdapat masalah dengan rekursi yang anda tulis, jika sempadan tidak dijumpai dengan betul, ia pasti akan melaporkan

, jika dilaporkan Ralat ini mestilah syarat penamatan anda salah, atau syarat penamatan tidak ditulis, yang menyebabkan kedalaman rekursi anda terlalu besar, dan akhirnya timbunan melimpah.

Jika kita mahu kod di atas betul, kita perlu menambah syarat penamatan padanya.

Kod yang betul adalah seperti berikut:

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

Berikut akan memberi anda pemahaman yang lebih mendalam tentang rekursi melalui contoh mudah

2. Penggunaan rekursi

Contoh : Cari faktorial bagi n secara rekursif Analisis lukisan:

Kod pelaksanaan:

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

Penerangan lukisan kod:

Contoh: Cari jumlah n

Analisis grafik:

Kod pelaksanaan:

第一种写法：
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));
 
    }
}

Contoh: Pelaksanaan rekursif mencetak setiap digit mengikut urutan

Analisis lukisan:

Kod pelaksanaan:

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

Contoh soalan : Tulis satu kaedah rekursif yang mengambil integer bukan negatif dan mengembalikan jumlah digitnya. Contohnya: jika anda memasukkan 1729, ia sepatutnya mengembalikan 1+7+2+9

Kod pelaksanaan:

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

Contoh soalan: Cari nombor Fibonacci ke-n

Analisis lukisan:

Kod pelaksanaan:

第一种方法：递归
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));
 
    }

Atas ialah kandungan terperinci Java Recursion: Konsep dan Penggunaan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!