Apakah teknik pengoptimuman untuk panggilan rekursif dalam fungsi Java?

Teknik untuk mengoptimumkan panggilan rekursif: Penghapusan rekursif ekor: Tukar rekursi ekor kepada gelung untuk menghapuskan limpahan tindanan. Lelaran dan bukannya rekursi: Gunakan gelung dan bukannya rekursi untuk menjimatkan kos panggilan fungsi. Memo: Menyimpan hasil pengiraan sebelumnya untuk mengurangkan bilangan panggilan rekursif.

Teknik Pengoptimuman untuk Panggilan Rekursif dalam Fungsi Java

Rekursi ialah teknik pengaturcaraan berkuasa yang membolehkan fungsi memanggil diri mereka sendiri. Walau bagaimanapun, rekursi boleh menyebabkan limpahan tindanan, terutamanya apabila panggilan fungsi terlalu dalam atau apabila set data diproses terlalu besar. Untuk mengoptimumkan panggilan rekursif, kita boleh menggunakan teknik berikut:

1. Penghapusan rekursif ekor

Rekursif ekor bermaksud fungsi memanggil dirinya sendiri dalam langkah terakhir. Mesin Maya Java boleh mengoptimumkan rekursi ekor dengan menukarnya menjadi gelung, dengan itu mengelakkan limpahan tindanan.

public static int factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1); // 尾递归调用
    }
}

2. Gunakan lelaran dan bukannya rekursi

Dalam sesetengah kes, kita boleh menggunakan gelung eksplisit dan bukannya rekursi. Ini menjimatkan overhed panggilan fungsi dan menghalang limpahan tindanan.

public static int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

3. Memo

Memo ialah teknik yang digunakan untuk menyimpan hasil yang dikira sebelum ini. Apabila fungsi memanggil dirinya semula, ia mula-mula menyemak sama ada keputusan wujud dalam memo. Jika ia wujud, hasilnya dikembalikan secara langsung, jika tidak, panggilan rekursif dibuat.

import java.util.HashMap;
import java.util.Map;

public static int factorial(int n) {
    Map<Integer, Integer> memo = new HashMap<>();
    return factorial(n, memo);
}

private static int factorial(int n, Map<Integer, Integer> memo) {
    if (n == 0) {
        return 1;
    } else if (memo.containsKey(n)) {
        return memo.get(n);
    } else {
        int result = n * factorial(n - 1);
        memo.put(n, result);
        return result;
    }
}

Contoh Praktikal

Pertimbangkan fungsi rekursif yang mengira jujukan Fibonacci:

public static int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2); // 递归调用
    }
}

Untuk nilai n besar, fungsi ini mungkin menyebabkan limpahan tindanan. Kita boleh mengoptimumkannya menggunakan penghapusan rekursi ekor:

public static int fibonacci(int n) {
    return fibonacci(n, 0, 1);
}

private static int fibonacci(int n, int prev, int current) {
    if (n == 0) {
        return prev;
    } else if (n == 1) {
        return current;
    } else {
        return fibonacci(n - 1, current, prev + current); // 尾递归调用
    }
}

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