java在遞歸函數中保留信息

Question

是否可以通過java的幫助函數保留信息，而不使用靜態變量。

例如，

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

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

即我想沒有鬆動爲每個遞歸情況下，信息更新變量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

爲什麼不把它變成一個實例變量（不一定是靜態的）......？

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 5

你可以返回一個列表或者類似的數據結構：

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 6

因爲變量v是原始類型，它所做的更改不會是功能範圍之外可見。你可以在類中聲明變量v，說狀態，並將狀態對象傳遞給遞歸函數以獲得所需的效果。

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 7

您可以傳遞一個對象來存儲每次遞歸調用的更新。像下面的那樣。

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

Answer 8

我認爲這叫做memoization。它看起來像

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

你應該能夠從這個算法中獲得體面的（不是最優的）性能。遞歸斐波那契算法性能糟糕的主要原因是b/c重複計算相同的值。通過遞歸+記憶，它不會多次計算任何值。

感謝@Aristide指出記憶和記憶之間的細微差別。