时间戳

首页 > 解决方案 > 考虑实现递归方法的最佳方式？

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

问题描述

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

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

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

我不确定采取什么方法来快速解决这样的问题（没有首先迭代地解决它并将其转换为尾递归，这需要很多时间）。

非常感谢一些提示，在此先感谢。

标签： javaalgorithmrecursiontail-recursion

解决方案

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

首先，首先检查小输入（称为角落/基本案例）。然后在小输入上构建它（手动通过空运行）。完成此操作后，在大多数情况下，您可以找出递归关系（如斐波那契中的此处）。测试其有效性，然后使用基本案例和当前递归关系，写一个递归。

例如，给定的代码在二叉树中搜索具有特定值的节点（如果您不知道二叉树是什么，请查看：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
}

推荐阅读