Quelles sont les alternatives aux appels récursifs dans les fonctions Java ?

Remplacez les appels récursifs dans les fonctions Java par l'itération

En Java, la récursivité est un outil puissant utilisé pour résoudre divers problèmes. Cependant, dans certains cas, l’utilisation de l’itération peut s’avérer une meilleure option car elle est plus efficace et moins sujette aux débordements de pile.

Voici les avantages de l'itération :

• Plus efficace car elle ne nécessite pas la création d'un nouveau stack frame pour chaque appel récursif.
• Le débordement de pile n'est pas susceptible de se produire car l'utilisation de l'espace de la pile est limitée.

Méthodes itératives au lieu d'appels récursifs :

Il existe plusieurs façons en Java de convertir une fonction récursive en fonction itérative.

1. Utilisez la pile

L'utilisation de la pile est le moyen le plus simple de convertir une fonction récursive en fonction itérative. La pile est une structure de données dernier entré, premier sorti (LIFO), similaire à une pile d'appels de fonction.

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. Utiliser des files d'attente

Vous pouvez également utiliser des files d'attente pour convertir des fonctions récursives en fonctions itératives. Une file d'attente est une structure de données premier entré, premier sorti (FIFO), similaire à une file d'attente de messages.

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. Simulez manuellement la pile d'appels de fonction

Vous pouvez également simuler manuellement la pile d'appels de fonction pour implémenter l'itération. Cela implique de maintenir explicitement un tableau de cadres de pile et de garder une trace du cadre de pile actuel via l'index du tableau.

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

Cas pratique : séquence de Fibonacci

Prenons la séquence de Fibonacci comme exemple pour illustrer comment utiliser l'itération au lieu de la récursivité.

// 递归
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();
}

En utilisant l'itération, nous évitons la surcharge des appels récursifs et améliorons l'efficacité.

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!