java - 変数なしで再帰呼び出しをカウントする

Question

変数なしで再帰の深さを数えることは可能ですか？

Answer 1

このようなものをお探しですか？

public int foo(int count) {
    if (exitCondition) return count; 
    foo(count+1);
}

呼び出しをカウントする他の方法には、リフレクションまたはバイトコード変更ライブラリ (つまり、AoP) の使用が含まれます。

Answer 2

ジャワで、

Thread.currentThread().getStackTrace()

呼び出しの深さを決定するために使用できます。再帰呼び出しの数は、スタックの長さと最初のフレームの位置の差です。

または、例外をスローしてから、次のように最上位の関数からスタックを取得します。

Throwable.getStackTrace()

それぞれが 1 つのスタック フレームを表すスタック トレース要素の配列を返します。配列の 0 番目の要素 (配列の長さがゼロでない場合) は、スタックの一番上を表し、これはシーケンス内の最後のメソッド呼び出しです。通常、これは、このスロー可能オブジェクトが作成およびスローされた時点です。配列の最後の要素 (配列の長さが 0 以外であると仮定) は、スタックの一番下を表します。これは、シーケンス内の最初のメソッド呼び出しです。

http://docs.oracle.com/javase/1.4.2/docs/api/java/lang/Throwable.html

Answer 3

あなたの質問は非常に漠然としているので、いくつかの仮定を立てています。

1. 「再帰呼び出しの数」とは、「再帰の深さ」を意味します
2. 関数の元の呼び出し元は深さを知りたいので、再帰メソッドはそれを返します
3. 「変数なし」とは、深さを追跡するためにローカル変数を使用することさえできないことを意味します

したがって、ランダムな方法で再帰関数を呼び出すと、次のようになります。

public void randomMethod() {
    Something somethingToRecurseOn = ... ;
    int depth = recurse(somethingToRecurseOn);
}

これは、私のソリューションの予想される使用法です。recurseメソッドは次のとおりです。

public int recurse(Something s) {
    Something subS = s.getSubS();
    if (subS == null) { // Exit condition
        return 1;
    }
    // Do something with subS
    return recurse(subS) + 1;
}

深さを関数の戻り値に統合し、終了条件の深さを 1 と想定します。

これは、私が過去に尋ねたインタビューの質問に実際に関連しています。そこでは、再帰シーケンスで要素の数を返す必要があり、署名は次のとおりです。

public int collatz(int n)

Wherenは、1 で停止するシーケンスの次の番号を見つけるために操作している番号です。反復ではなく再帰で実装されている場合、本質的に再帰の深さを返します。