考虑实现递归方法的最佳方式？

Question

所以我想知道你们中是否有人可以给我一些提示。我一直在做一些挑战，比如（经典的）制作一种方法来使用单个递归调用来计算斐波那契数列的第 n 个数（又名。避免 return fibo(n-1) + fibo(n-2);）。

我真的在那个问题上摸不着头脑，最后查看了使用辅助方法的解决方案 -

public static int fibonacci(int n) {
    if (n < 2) {
        return n;
    }
    return fibonacci_helper(n, 1, 0);
}

public static int fibonacci_helper(int n, int previous, int current) {
    if (n < 1) {
        return current;
    }
    return fibonacci_helper(n - 1,  current, previous + current);
}

我不太确定采用什么方法可以快速解决此类问题（无需先迭代解决并将其转化为尾递归，这会花费大量时间）。

非常感谢一些提示，提前致谢。

Answer 1

您正在考虑的领域称为动态规划。它的工作方式是，您尝试解决的较大问题的解决方案由较小问题的解决方案组成，如果您保留这些解决方案并重用它们，而不是多次计算它们，则时间复杂度可以大大降低。一般采用的方法是考虑如何分解问题，以及您需要记住哪些较小问题的解决方案才能解决它。在这种情况下，您可以通过将所有结果保存在一个数组中以线性时间和线性 space 来完成，如果您正在寻找 DP 解决方案，这应该很容易想到。当然这可以简化，因为您不需要保留所有这些数字，但这是一个单独的问题。

通常，DP 解决方案将是迭代的而不是递归的，因为您需要保留大量可用的解决方案来计算下一个更大的解决方案。要将其更改为使用递归，您只需要弄清楚需要传递哪些解决方案，并将其作为参数包含在内即可。

Answer 2

您需要首先确定问题是否需要递归 solution.Typically 当当前解决方案依赖于某些先前（已计算）的解决方案时，需要递归。

首先，首先检查小输入（称之为 corner/base 个案例）。然后在它的基础上（通过干运行手动）在小 inputs.Once 上你已经完成了这个，在大多数情况下，你可以找出递归关系（就像斐波那契中的这里）。测试它的有效性，并且然后使用基本情况和当前递归关系，写一个递归。

例如，给定的代码在二叉树中搜索具有特定值的节点（如果您不知道二叉树是什么，请查看：https://en.wikipedia.org/wiki/Binary_tree）

bool search(Node root,int val){

   if(root==null)//base case 1
     return false;
   if(root.value==val)//base case 2
     return true;
   return(search(root.left,val)||search(root.right,val));//recursing left and right subtrees for looking out for the value
}

Answer 3

在纸上玩一下，尝试发现隐藏的不必要重做的计算。然后尽量避开它们。

这里有f(n) = f(n-1) + f(n-2)；显然 f(n-1) = f(n-2) + f(n-3) 不必要地重做了 f(n-2)，等等等等。如果你可以同时做这两个呢？

有f2(n) return 两个值，n和(n-1)；然后你做（在伪代码）

f(n) = let { (a,b) := f2(n-1) } in (a+b)

现在你有两个函数，none还没有定义，有什么用呢？把这个 f 也变成 f2，所以它 return 有两个值，而不是一个，正如我们期望的那样：

f2(n) = let { (a,b) := f2(n-1) } in (a+b,a)

瞧，一个递归定义，其中 a 被重用。

剩下的就是添加一些 corner/edge/base 个案例，并检查 off-by-1 错误。

甚至更好，reverse the time arrow，从基本案例开始，并免费获得您的迭代版本。

递归是一种工具，可以帮助我们，。

考虑实现递归方法的最佳方式？

Best way to think about implementing recursive methods?

java

algorithm

recursion

tail-recursion