java - 分割递归可以手动完成吗？

Question

我有这个工作表问题需要解决，但我只是不知道如何手动完成它。每个方法都会再调用 2 个方法来运行，因此每个方法都会再调用 2 个方法。我不知道如何跟踪其中的任何一个。我不知道除了将其放入 Eclipse 之外如何找到答案。

static int fun(int x) {
    if(x < 1) {
        return 1;
    } else {
        return x + fun(x-1) + fun(x-2);
    }
}

public static void main(String[] args) {
    System.out.println(fun(4));
}

Answer 1

更简单的解决方案:声明一个足够大的数组以将 fun() 的值保存到您需要的值。当请求 fun(4) 时，您需要一个 int[5]。填充前两个元素的硬编码值，然后在循环中使用公式填充剩余条目。现在您的结果位于最后一个元素中。

可能的空间需求优化:在整个循环中，您始终只需要最后两个值和当前值，因此不需要将所有值存储在大小为 x + 1 的数组中。