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

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

在纸上玩它，并尝试发现隐藏的计算，重新做不必要的。那就尽量避开他们。

这里有f(n) = f(n-1) + f(n-2)；显然，f(n-1) = f(n-2) + f(n-3)没有必要地重做f(n-2)，等等等等。如果你能同时做这两件事呢？

让f2(n)返回两个值，用于n和(n-1)；然后返回(伪代码)

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

现在有两个函数，还没有定义，它有什么好处？将此f也转换为f2，因此它返回两个值，而不是像我们预期的那样返回一个：

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

和瞧，这是一个递归的定义，其中a被重用。

剩下的就是添加一些角/边/基大小写，并检查关闭-1错误。

或者更好的是，倒转时间箭头，从基本情况开始，免费获得迭代版本。

递归是一个帮助我们的工具，用于使问题解决。

Answer 2

您需要首先决定这个问题是否需要递归的solution.Typically，当当前的解决方案依赖于以前的(已经计算的)解决方案时，就需要递归。

首先，首先检查小输入(称为角/基情况)。然后在小型inputs.Once上构建它(手动运行)--在大多数情况下，您可以计算出递归关系(如fibonacci中的这里)--.Test它的有效性，然后使用基本情况和当前递归关系，编写一个递归。

例如，给定的代码搜索二叉树中具有特定值的节点(如果不知道二叉树是什么：树)

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

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

通常，DP解决方案将是迭代的，而不是递归的，因为您需要保持大量可用的解决方案来计算下一个更大的解决方案。要将其更改为使用递归，只需确定需要传递哪些解决方案，并将这些作为参数。