Apakah alternatif kepada panggilan rekursif dalam fungsi Java?

Ganti panggilan rekursif dalam fungsi Java dengan lelaran

Di Java, rekursi ialah alat berkuasa yang digunakan untuk menyelesaikan pelbagai masalah. Walau bagaimanapun, dalam beberapa kes, menggunakan lelaran mungkin merupakan pilihan yang lebih baik kerana ia lebih cekap dan kurang terdedah kepada limpahan tindanan.

Berikut adalah kelebihan lelaran:

• Lebih cekap kerana ia tidak memerlukan penciptaan bingkai tindanan baharu untuk setiap panggilan rekursif.
• Limpahan timbunan tidak mudah berlaku kerana penggunaan ruang timbunan adalah terhad.

Kaedah berulang dan bukannya panggilan rekursif:

Terdapat beberapa cara dalam Java untuk menukar fungsi rekursif kepada fungsi berulang.

1. Gunakan tindanan

Menggunakan tindanan ialah cara paling mudah untuk menukar fungsi rekursif kepada fungsi berulang. Tindanan ialah struktur data masuk-dahulu-keluar (LIFO), serupa dengan timbunan panggilan fungsi.

public int factorial(int n) {
    Stack<Integer> stack = new Stack<>();
    stack.push(n);
    while (!stack.isEmpty()) {
        int curr = stack.pop();
        if (curr == 1) {
            return 1;
        }
        stack.push(curr - 1);
        stack.push(curr);
    }
}

2. Menggunakan baris gilir

Anda juga boleh menggunakan baris gilir untuk menukar fungsi rekursif kepada fungsi berulang. Baris gilir ialah struktur data masuk dahulu, keluar dahulu (FIFO), serupa dengan baris gilir mesej.

public int factorial(int n) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(n);
    while (!queue.isEmpty()) {
        int curr = queue.poll();
        if (curr == 1) {
            return 1;
        }
        queue.offer(curr - 1);
        queue.offer(curr);
    }
}

3 Simulasikan tindanan panggilan fungsi secara manual

Anda juga boleh mensimulasikan tindanan panggilan fungsi secara manual untuk melaksanakan lelaran. Ini melibatkan secara eksplisit mengekalkan tatasusunan bingkai tindanan dan menjejaki bingkai tindanan semasa melalui indeks tatasusunan.

public int factorial(int n) {
    int[] stack = new int[100];
    int top = -1;
    stack[++top] = 1;
    stack[++top] = n;
    while (top > 0) {
        int curr = stack[top--];
        if (curr == 1) {
            return stack[top--];
        }
        stack[++top] = curr - 1;
        stack[++top] = curr;
    }
}

Kes Praktikal: Jujukan Fibonacci

Mari kita ambil Jujukan Fibonacci sebagai contoh untuk menggambarkan cara menggunakan lelaran dan bukannya rekursi.

// 递归
public int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

// 迭代（使用队列）
public int fib(int n) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(0);
    queue.offer(1);
    while (n-- > 1) {
        int a = queue.poll();
        int b = queue.poll();
        queue.offer(a + b);
    }
    return queue.poll();
}

Dengan menggunakan lelaran, kami mengelakkan overhed panggilan rekursif dan meningkatkan kecekapan.

Atas ialah kandungan terperinci Apakah alternatif kepada panggilan rekursif dalam fungsi Java?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!