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指出记忆和记忆之间的细微差别。