以最少的运行时间存储具有递归的斐波那契序列的值

Question

我知道我的代码现在有很多问题，但是我只是想在尝试任何事情之前得到正确的想法。我需要有一个方法来接受一个整数n，它返回斐波那契序列中的第n个数字。当用递归正常求解它时，我必须最小化运行时间，这样当它得到像第45个整数一样的东西时，它仍然会运行得相当快。此外，我不能使用类常量和全局变量。

递归的正常方式。

public static int fibonacci(int n) {
    if (n <= 2) { // to indicate the first two elems in the sequence 
        return 1;
    } else { // goes back to very first integer to calculate (n-1) and (n+1) for (n)
        return fibonacci(n-1) + fibonacci(n-2); 
    }
}

我认为问题是这个过程中有很多冗余。我想我可以创建一个列表来计算多达n个元素，这样在返回第n个元素之前它只运行一次。然而，在这种情况下，我很难看到如何使用递归。

如果我理解正确，标准递归方法很慢，因为有很多重复：

fib（6）=fib（5）fib（4）

fib（5）=fib（4）fib（3）

fib（4）=fib（3）1

fib（3）=1 1

这是解决这个问题的正确方法吗？它需要某种形式的容器来获得更快的输出，同时仍然是递归的吗？我应该使用帮助方法吗？我最近才开始使用递归编程，因为我已经习惯了迭代方法，所以很难理解这一点。谢谢。

这是我有缺陷且未完成的代码：

public static int fasterFib(int n) {
    ArrayList<Integer> results = new ArrayList<Integer>();
    if (n <= 2) { // if 
        return 1;
    } else if (results.size() <= n){ // If the list has fewer elems than 
        results.add(0, 1);
        results.add(0, 1);
        results.add(results.get(results.size() - 1 + results.get(results.size() - 2)));
        return fasterFib(n); // not sure what to do with this yet
    } else if (results.size() == n) { // base case if reached elems
        return results.get(n);
    }
    return 0;
}

Answer 1

另一种方法是使用助手方法。

static private int fibonacci(int a, int b, int n) {
  if(n == 0) return a;
  else return fibonacci(b, a+b, n-1);
}

static public int fibonacci(int n) {
  return fibonacci(0, 1, n);
}

Answer 2

您可以使用Map：：ComputeFabSent方法（从1.8开始）重新使用已经计算的数字。

import java.util.HashMap;
import java.util.Map;

public class Fibonacci {

    private final Map<Integer, Integer> cache = new HashMap<>();

    public int fib(int n) {
        if (n <= 2) {
            return n;
        } else {
            return cache.computeIfAbsent(n, (key) -> fib(n - 1) + fib(n - 2));
        }
    }
}

Answer 3

我想你应该用地图

private static Map<Integer, Integer> results = new HashMap<>();

public static int fasterFib(int n) {
  if (n == 0) {
    return 0;
  } else if (n <= 2) { // if
    return 1;
  }
  if (results.get(n) != null) {
    return results.get(n);
  } else {
    int v = fasterFib(n - 1) + fasterFib(n - 2);
    results.put(n, v);
    return v;
  }
}

这种优化被称为记忆，来自维基百科的文章——

在计算中，记忆是一种优化技术，主要用于通过保留昂贵函数调用的结果并在相同输入再次出现时返回缓存结果来加速计算机程序。