java在递归函数中保留信息
是否可以通过java的辅助函数保留信息，而不使用静态变量。
例如，
public void foo(){ int v = 0; fooHelper(2); } public void fooHelper(int depth){ v++; fooHelper(depth-1) } 也就是说，我想更新变量v而不丢失每个递归情况的信息，而不必访问函数外部的变量。
忘记告诉您声明属性的所有答案，或者在每次递归调用中更新可变对象。 在真正的函数式递归样式中，通过将其作为参数和/或返回类型传递来“保留”信息。
让我用一个简单的例子来说明，假设你想要递归地计算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()的值。
在范围中声明的变量（例如方法）只能在此范围内访问（例如，不在另一种方法中）。
如果信息仅与方法相关，请将变量保留在方法中。 如果信息与整个对象/类状态相关，请将其保留为类成员（静态/非静态）。
例如：
public void someRecursiveMethod(int num) { while (num < 10) { num++; someRecursiveMethod(num); System.out.println("Current num = " + num); } }
您可以创建一个新类（yuck），或将该变量作为参数传递并在fooHelper中返回。
为什么不把它变成一个实例变量（不一定是静态的）……
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(); } }
您可以返回列表或类似的数据结构：
public List fooHelper( int v, int depth ){ if( depth == 0 ) return new ArrayList(); v++; List result = fooHelper( v, depth-1 ); result.add( new Integer(v) ); return result; }
因为变量v是基本类型，所以对它做出的更改在函数范围之外是不可见的。 您可以在类中声明变量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; }
希望能帮助到你。
您可以传递一个对象来存储每个递归调用的更新。 像下面那样的东西。
public static void fooHelper(int depth, HashMap map){ map.put(depth, "Call " + depth); if (depth > 0) { fooHelper(depth-1, map); } return; }
我认为这称为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它重复计算相同的值。 使用递归+ memoization，它永远不会计算任何值。
感谢@Aristide指出了记忆和记忆之间的细微差别。