递归到迭代(java)

Question

作为编程的初学者,我试图将以下递归方法转换为迭代方法,但我只是不了解它.方法或函数有一个二进制树,如递归,我想使用一个数组的迭代解决方案..不幸的是,我很困惑如何做到这一点.

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

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个成员.首先添加前两个已知成员.Fibonacci更容易,因为你总是只需要以前的价值.

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