Java Language
再帰

前書き

備考

再帰の基本的な考え方

再帰とは何ですか？

一般に、再帰は、関数が直接的または間接的にそれ自身を呼び出すときです。例えば：

// This method calls itself "infinitely"
public void useless() {
    useless();  // method calls itself (directly)
}

問題への再帰を適用するための条件：

再帰関数を使用して特定の問題を解決するには、次の2つの前提条件があります。

1. 問題の基本条件がなければなりません。これは再帰の終点になります。再帰関数が基本条件に達すると、それ以上の（深い）再帰呼び出しは行われません。

2. 各レベルの再帰は、より小さな問題を試みるべきです。したがって、再帰関数は問題をより小さい部分に分割します。問題が有限であると仮定すると、再帰が終了することが保証されます。

Javaでは、3番目の前提条件があります。問題を解決するにはあまりにも深く再帰する必要はありません。 深い再帰がJavaで問題になる

例

次の関数は、再帰を使用して階乗を計算します。メソッドfactorialが関数内でどのように自身を呼び出すかに注目してください。自身を呼び出すたびに、パラメータnを1減らしますnが1になると（ベース条件）、関数はそれ以上深く再帰しません。

public int factorial(int n) {
    if (n <= 1) { // the base condition 
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

^{これは整数オーバーフロー、またはn大きな値に対するコールスタックオーバーフロー（すなわちStackOverflowError例外）を考慮していないため、Javaの階乗を計算する実際的な方法ではありません。}

N番目のフィボナッチ数の計算

次のメソッドは、再帰を使用してN番目のフィボナッチ数を計算します。

public int fib(final int n) {
    if (n > 2) {
        return fib(n - 2) + fib(n - 1);
    }
    return 1;
}

メソッドは、基底ケース（n <= 2）と再帰ケース（n> 2）を実装します。これは、再帰的関係を計算するために再帰を使用することを示しています。

しかしながら、この例は例示的なものであるが、非効率的である。すなわち、メソッドの各単一インスタンスは、関数自体を2回呼び出すため、Nが増加するにつれて関数が呼び出される回数が指数関数的に増加する。上記の関数はO（2 ^N ）ですが、同等の反復解は複雑さO（N）を持ちます。さらに、O（N）浮動小数点乗算で評価できる「閉じた形式」の式があります。

1からNまでの整数の合計を計算する

次のメソッドは、再帰を使用して0からNまでの整数の合計を計算します。

public int sum(final int n) {
    if (n > 0) {
        return n + sum(n - 1);
    } else {
        return n;
    }
}

この方法はO（N）であり、テールコール最適化を使用して単純なループに減らすことができます。実際、 O(1)操作で合計を計算する閉じた形式の式があります。

数のN乗を計算する

次のメソッドは、再帰を使用してnumの値をexpの累乗にして計算します。

public long power(final int num, final int exp) {
    if (exp == 0) {
        return 1;
    }
    if (exp == 1) {
        return num;
    }
    return num * power(num, exp - 1);
}

再帰メソッドは、再帰を終了させる基本ケース（2つのケース、n = 0およびn = 1）と、そのメソッドを再度呼び出す再帰的ケースを実装します。この方法はO（N）であり、テールコール最適化を使用して単純なループに減らすことができます。

再帰を使用して文字列を反転する

以下は、文字列を逆順にするための再帰的なコードです

/**
 * Just a snippet to explain the idea of recursion
 *
 **/

public class Reverse {
    public static void main (String args[]) {
        String string = "hello world";
        System.out.println(reverse(string)); //prints dlrow olleh
    }

    public static String reverse(String s) {
        if (s.length() == 1) {
            return s;
        }
    
        return reverse(s.substring(1)) + s.charAt(0);
    }
}

再帰によるツリーデータ構造のトラバース

以下のように、3つのメンバーデータ、左の子ポインター、および右の子ポインターを持つNodeクラスを考えてみましょう。

public class Node {
    public int data;
    public Node left;
    public Node right;
    
    public Node(int data){
        this.data = data;
    }
}

以下のように複数のNodeクラスのオブジェクトを接続して構築したツリーを横断することができます。このトラバーサルは、ツリーの順序通りのトラバーサルと呼ばれます。

public static void inOrderTraversal(Node root) {
        if (root != null) {          
            inOrderTraversal(root.left); // traverse left sub tree
            System.out.print(root.data + " "); // traverse current node
            inOrderTraversal(root.right); // traverse right sub tree
        }
    }

上で示したように、 反復を使用すると、 繰り返しアプローチでは不可能な他のデータ構造を使用することなく、 ツリーデータ構造をトラバースすることができます。

再帰のタイプ

再帰は、再帰的メソッド呼び出しの配置場所に応じて、 Head RecursionまたはTail Recursionのいずれかに分類できます。

頭部再帰では、再帰呼び出しは、関数が発生したときに関数の他の処理の前に来ます（関数の先頭や頭部で起こったと考えてください）。

末尾再帰では、逆のことです。再帰呼び出しの前に処理が行われます。 2つの再帰的スタイルの中から選択することは任意であるかもしれませんが、その選択はすべての違いを生むことができます。

パスの先頭に単一の再帰呼び出しを持つパスを持つ関数は、頭部再帰と呼ばれるものを使用します。以前の展示の階乗関数は頭部再帰を使用します。再帰が必要であると判断した最初のことは、減分されたパラメータで自身を呼び出すことです。パスの終わりに単一の再帰呼び出しを持つ関数は、末尾再帰を使用しています。

public void tail(int n)              public void head(int n)
{                                       {
   if(n == 1)                             if(n == 0)
      return;                                return;
   else                                   else
      System.out.println(n);                 head(n-1);

   tail(n-1);                              System.out.println(n);
}                                        }

再帰呼び出しがメソッドの最後に発生した場合、それはtail recursionと呼ばれtail recursion 。テール再帰はsimilar to a loop 。このmethod executes all the statements before jumping into the next recursive call 。

再帰呼び出しがbeginning of a method, it is called a head recursionのbeginning of a method, it is called a head recursion発生する場合、再帰呼び出しbeginning of a method, it is called a head recursion 。このmethod saves the state before jumping into the next recursive call 。

参照： head＆tail再帰の違い

StackOverflowErrorおよびループへの再帰

再帰呼び出しが "深すぎ"になると、 StackOverflowErrorます。 Javaはスレッドのスタック上のすべてのメソッド呼び出しに新しいフレームを割り当てます。しかし、各スレッドのスタックのスペースは限られています。スタック上のフレームが多すぎると、スタックオーバーフロー（SO）が発生します。

例

public static void recursion(int depth) {
    if (depth > 0) {
        recursion(depth-1);
    }
}

このメソッドを大きなパラメータで呼び出すと（おそらくrecursion(50000) 、スタックのオーバーフローが発生します。正確な値はスレッドのスタックサイズ、スレッド構成、 -Xssなどのコマンドラインパラメータ、またはJVMのデフォルトサイズ。

回避策

再帰呼び出しごとのデータをデータ構造に格納することで、再帰をループに変換することができます。このデータ構造は、スレッドスタックではなくヒープに格納することができます。

一般に、メソッド呼び出しの状態を復元するために必要なデータはスタックに格納でき、whileループは再帰呼び出しを「シミュレート」するために使用できます。必要なデータには次のものがあります。

• メソッドが呼び出されたオブジェクト（インスタンスメソッドのみ）
• メソッドのパラメータ
• 局所変数
• 実行またはメソッドの現在の位置

例

次のクラスでは、特定の深さまでツリー構造を再帰的に印刷することができます。

public class Node {

    public int data;
    public Node left;
    public Node right;

    public Node(int data) {
        this(data, null, null);
    }

    public Node(int data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public void print(final int maxDepth) {
        if (maxDepth <= 0) {
            System.out.print("(...)");
        } else {
            System.out.print("(");
            if (left != null) {
                left.print(maxDepth-1);
            }
            System.out.print(data);
            if (right != null) {
                right.print(maxDepth-1);
            }
            System.out.print(")");
        }
    }

}

例えば

Node n = new Node(10, new Node(20, new Node(50), new Node(1)), new Node(30, new Node(42), null));
n.print(2);
System.out.println();

プリント

(((...)20(...))10((...)30))

これは次のループに変換することができます：

public class Frame {

    public final Node node;

    // 0: before printing anything
    // 1: before printing data
    // 2: before printing ")"
    public int state = 0;
    public final int maxDepth;

    public Frame(Node node, int maxDepth) {
        this.node = node;
        this.maxDepth = maxDepth;
    }

}

List<Frame> stack = new ArrayList<>();
stack.add(new Frame(n, 2)); // first frame = initial call

while (!stack.isEmpty()) {
    // get topmost stack element
    int index = stack.size() - 1;
    Frame frame = stack.get(index); // get topmost frame
    if (frame.maxDepth <= 0) {
        // termial case (too deep)
        System.out.print("(...)");
        stack.remove(index); // drop frame
    } else {
        switch (frame.state) {
            case 0:
                frame.state++;

                // do everything done before the first recursive call
                System.out.print("(");
                if (frame.node.left != null) {
                    // add new frame (recursive call to left and stop)
                    stack.add(new Frame(frame.node.left, frame.maxDepth - 1));
                    break;
                }
            case 1:
                frame.state++;

                // do everything done before the second recursive call
                System.out.print(frame.node.data);
                if (frame.node.right != null) {
                    // add new frame (recursive call to right and stop)
                    stack.add(new Frame(frame.node.right, frame.maxDepth - 1));
                    break;
                }
            case 2:
                // do everything after the second recursive call & drop frame
                System.out.print(")");
                stack.remove(index);
        }
    }
}
System.out.println();

注：これは一般的なアプローチの単なる例です。しばしば、フレームを表現する、および/またはフレームデータを格納する、より良い方法を考え出すことができます。

Javaで深い再帰が問題になる

再帰を使用して2つの正の数を追加するための以下の単純な方法を考えてみましょう。

public static int add(int a, int b) {
    if (a == 0) {
        return b;
    } else {
        return add(a - 1, b + 1);  // TAIL CALL
    }
}

これはアルゴリズム的には正しいですが、大きな問題があります。大きなa add使ってaddを呼び出すと、 StackOverflowError 、少なくともJava 9以降のJavaバージョンでクラッシュします。

典型的な関数型プログラミング言語（および他の多くの言語）では、コンパイラは末尾再帰を最適化します 。コンパイラはadd （タグ付き行で） addの呼び出しがテールコールであり、ループとして再帰を効果的に書き換えることに気付くでしょう。この変換はテールコール除去と呼ばれます。

しかし、現世代のJavaコンパイラは、テール・コール除去を実行しません。代わりに、 add各再帰呼び出しによってスレッドのスタックに新しいフレームが割り当てられます。たとえば、 add(1000, 1)呼び出すと、 1000再帰呼び出しがあり、 1001の応答になります。

問題は、スレッドが作成されるときにJavaスレッドスタックのサイズが固定されることです。 （これには、シングルスレッドプログラムの「メイン」スレッドも含まれます）。スタックフレームが多すぎると、スタックがオーバーフローします。 JVMはこれを検出してStackOverflowErrorをスローします。

これに対処する1つのアプローチは、単により大きなスタックを使用することです。スタックのデフォルトサイズを制御するJVMオプションがあり、スタックサイズをThreadコンストラクタパラメータとして指定することもできます。残念ながら、これはスタックのオーバーフローを「止め」ます。さらに大きなスタックを必要とする計算を行う必要がある場合は、 StackOverflowErrorが返されます。

実際の解決策は、深い再帰が発生する可能性がある再帰アルゴリズムを特定し、ソースコードレベルでテールコール最適化を手動で実行することです。たとえば、次のようにaddメソッドを書き換えることができます。

public static int add(int a, int b) {
    while (a != 0) {
       a = a - 1;
       b = b + 1;
    }
    return b;
}

（明らかに、2つの整数を追加するより良い方法があります。上記は、手動によるテールコール除去の効果を説明するためのものです。）

なぜテールコール除去がJavaではまだ実装されていないのですか？

Javaへのテール・コールの削除を追加するのは簡単ではありません。例えば：

• いくつかのコードは、 StackOverflowErrorに依存して（例えば）計算上の問題の大きさに制限をStackOverflowErrorことができます。
• サンドボックスのセキュリティ管理者は、特権のないコードで特権アクションを実行するかどうかを決定する際に、コールスタックを分析することがしばしば役に立ちます。

John Roseが「VMのテールコール」で説明したように ：

呼び出し元のスタックフレームを削除することによる影響は、いくつかのAPI、特にアクセスコントロールのチェックやスタックトレースから見ることができ、呼び出し元の呼び出し元が呼び出し先を直接呼び出したかのようです。ただし、呼び出し先メソッドのリンケージとアクセシビリティは、コントロールの転送前に計算され、末尾呼び出しの呼び出し元を考慮に入れます。

言い換えれば、テール・コールを削除すると、アクセス制御メソッドは、機密保護されたAPIが信頼できるコードによって呼び出されていると誤って判断する可能性があります。