Java 関数での再帰呼び出しの代替手段は何ですか?

反復を使用して Java 関数の再帰呼び出しを置き換える

Java では、再帰はさまざまな問題を解決するために使用される強力なツールです。ただし、場合によっては、反復を使用する方が効率が高く、スタック オーバーフローが発生しにくいため、より良いオプションになる場合があります。

反復の利点は次のとおりです。

• 再帰呼び出しごとに新しいスタック フレームを作成する必要がないため、より効率的です。
• スタックスペースの使用量が限られているため、スタックオーバーフローは発生しにくいです。

再帰呼び出しではなく反復メソッド:

Java には、再帰関数を反復関数に変換する方法がいくつかあります。

1. スタックの使用

スタックの使用は、再帰関数を反復関数に変換する最も簡単な方法です。スタックは、関数呼び出しスタックに似た、後入れ先出し (LIFO) データ構造です。

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. キューの使用

キューを使用して、再帰関数を反復関数に変換することもできます。キューは、メッセージ キューに似た先入れ先出し (FIFO) データ構造です。

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. 関数呼び出しスタックを手動でシミュレートする

関数呼び出しスタックを手動でシミュレートして反復を実現することもできます。これには、スタック フレームの配列を明示的に維持し、配列インデックスを介して現在のスタック フレームを追跡することが含まれます。

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

実践的なケース: フィボナッチ数列

再帰の代わりに反復を使用する方法を説明するために、フィボナッチ数列を例に挙げてみましょう。

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

反復を使用することで、再帰呼び出しのオーバーヘッドを回避し、効率を向上させます。

以上がJava 関数での再帰呼び出しの代替手段は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。