java - 递归到迭代(java)

Question

作为编程初学者，我试图将以下递归方法转换为迭代方法，但我就是不明白它的窍门。该方法或函数有一个类似递归的二叉树，我想使用一个数组作为迭代解决方案。不幸的是，我很困惑如何去做。

我已经检查了将斐波那契递归方法转换为迭代方法的方法。但我认为这里不一样。另外我不确定树搜索方法是否有用？!任何帮助，提示，想法将不胜感激。谢谢。

public static int funct(int n) {

  if (n == 0) return 1;
  if (n == 1) return 2;
  if n > 1 return funct(n-2)*funct(n/2);

}

Answer 1

如果您可以将所有内容缓存在一个列表中，那么之前每个第 n 个成员都由其他人计算过。您首先添加前 2 个已知成员。斐波那契更容易，因为你总是只需要以前的值(value)。

private static int func(int n) {
    List<Integer> values = new ArrayList<>(n+1);
    values.add(1);
    values.add(2);
    for (int i = 2; i <= n; i++) {
        values.add(values.get(i - 2) * values.get(i / 2));
    }

    return values.get(n);
}