Javaは再帰関数内に情報を保持します

Question

静的変数を使用せずにjavaを使用してヘルパー関数を介して情報を保持することは可能ですか？例えば

、

public void foo(){ 
    int v = 0; 
    fooHelper(2); 
} 

public void fooHelper(int depth){ 
    v++; 
    fooHelper(depth-1) 
} 

、すなわちIは、関数外の変数にアクセスすることなく、各再帰ケースの情報を失うことなく、変数vを更新します。

Answer 1

属性を宣言するか、各再帰呼び出しで変更可能なオブジェクトを更新するように指示するすべての回答を忘れてしまいます。真の機能、再帰的スタイルでは、パラメータや戻り値の型として渡すことで情報を "保持"します。

簡単な例で説明しますが、int[]の要素の合計を再帰的に計算したいとします。ここで、の状態（再帰呼び出しの間に保持する必要のある情報）は、配列内の現在のインデックスおよびこれまでの合計です。ここでそれを行う方法は次のとおりです。

public int sum(int[] array) { 
    return sum(array, 0, 0); 
} 

private int sum(int[] array, int idx, int acc) { 
    if (idx == array.length) 
     return acc; 
    return sum(array, idx+1, acc+array[idx]); 
} 

はこのようにそれを呼び出していない：属性あなたが見ることができるように、（静的またはインスタンス）を宣言する必要はありません

int[] array = {1, 2, 3}; 
System.out.println(sum(array)); 

、そして合格し、可変変更する必要オブジェクト（リスト、マップ） - 問題を解決するために必要なすべての情報がメソッドパラメータとして存在するため、ローカル変数も使用していません。

v変数のコードでは、答えがaccであることを想定しています。すなわち、再帰が呼び出されるたびに累積された値が変更されます。最後に、累積値をヘルパー関数（void戻り値の型を持たないもの）から返す必要があります。その値はfoo()になります。

Answer 2

スコープで宣言された変数（メソッドなど）は、このスコープ内でのみアクセス可能です（別のメソッドでは使用できません）。

この情報がメソッドにのみ関連する場合は、変数をメソッドに保持します。情報がオブジェクト/クラス状態全体に関連する場合は、クラスメンバー（静的/非静的）のままにしておきます。例えば

：

public void someRecursiveMethod(int num) { 
    while (num < 10) { 
     num++; 
     someRecursiveMethod(num); 
     System.out.println("Current num = " + num); 
    } 
} 

Answer 3

あなたは新しいクラス（不潔）を作成、またはパラメータとして変数を渡し、fooHelperでそれを返すことができます。

Answer 4

なぜインスタンス変数にしないのですか（必ずしも静的ではない）...？変数vがプリミティブ型であるので、それに加えられた変更は、関数のスコープ外で表示されません、

public List<Integer> fooHelper(int v, int depth){ 
    if(depth == 0) return new ArrayList(); 

    v++; 
    List<Integer> result = fooHelper(v, depth-1); 

    result.add(new Integer(v)); 

    return result; 
} 

Answer 5

あなたがリストまたは類似のデータ構造を返すことができます。変数vをクラス内で宣言することができます。たとえば、Stateを指定し、状態オブジェクトを再帰関数に渡して、必要な効果を得ることができます。

public void foo(){ 
    State state = new State(); 
    fooHelper(state, 2); 
} 

public void fooHelper(State state, int depth){ 
    state.v++; 
    fooHelper(state, depth-1); 
} 

class State { 
    int v; 
} 

希望します。

Answer 6

：

public class Recursive { 
    int v = 0; 
    public void foo(){ 

     fooHelper(2); 
     System.out.println(v); 
    } 

    public void fooHelper(int depth){ 
     v++; 
     if(depth-1!=0)//Added this because I was getting an StackOverflowError 
     fooHelper(depth-1); 
    } 

    public static void main(String[] args) { 
     Recursive r = new Recursive(); 
     r.foo(); 
    } 
} 

Answer 7

各再帰呼び出しの更新を格納するオブジェクトを渡すことができます。下のようなもの。

public static void fooHelper(int depth, HashMap map){ 
     map.put(depth, "Call " + depth); 
     if (depth > 0) 
     { 
     fooHelper(depth-1, map); 
     } 
     return; 
    } 

Answer 8

私はこれをメモ化といいます。あなたはこのアルゴリズムのうち、まともな（最適ではない）のパフォーマンスを得ることができる必要があり

class Fibonacci 
{ 
    public Map < Integer , Integer > memorized = new HashMap < > () ; 

    public int fib (int n) 
    { 
      if (memoized . containsKey (n)) 
      { 
       return memoized . get (n) ; 
      } 
      else 
      { 
       int fib = // calculate recursively 
       memoized . put (n , fib) ; 
       return fib ; 
      } 
    } 
} 

ように見えます。再帰フィボナッチアルゴリズムが恐ろしい性能を持つ主な理由は、同じ値を繰り返し計算していることです。再帰+メモでは、何度も何度も計算することはありません。

メモリとメモの微妙な違いを指摘してくれた@Aristideに感謝します。