Java ExecutorService 解决递归斐波那契数列

Question

我需要使用线程递归地根据斐波那契数列中的某个索引找出数字，我尝试了以下代码，但程序永远不会结束。如果我遗漏了什么，请告诉我。

代码:

  import java.math.BigInteger;
  import java.util.concurrent.*;

  public class MultiThreadedFib {

    private ExecutorService executorService;

    public MultiThreadedFib(final int numberOfThreads) {
      executorService = Executors.newFixedThreadPool(numberOfThreads);
    }

    public BigInteger getFibNumberAtIndex(final int index) 
      throws InterruptedException, ExecutionException {

      Future<BigInteger> indexMinusOne = executorService.submit(
        new Callable<BigInteger>() {
          public BigInteger call() 
          throws InterruptedException, ExecutionException {
            return getNumber(index - 1);
          }
      });

      Future<BigInteger> indexMinusTwo = executorService.submit(
        new Callable<BigInteger>() {
          public BigInteger call() 
          throws InterruptedException, ExecutionException {
            return getNumber(index - 2);
          }
      });

      return indexMinusOne.get().add(indexMinusTwo.get());
    }

    public BigInteger getNumber(final int index) 
    throws InterruptedException, ExecutionException {
      if (index == 0 || index == 1)
        return BigInteger.valueOf(index);

      return getFibNumberAtIndex(index - 1).add(getFibNumberAtIndex(index - 2));
    }
  }

已修复(感谢 Fiver)

我不是从 call 方法中调用 getNumber(int)，而是调用计算该索引处的数字的动态编程算法。

其代码是:

public class DynamicFib implements IFib {

private Map<Integer, BigInteger> memoize = new HashMap<Integer, BigInteger>();

public DynamicFib() {
  memoize.put(0, BigInteger.ZERO);
  memoize.put(1, BigInteger.ONE);
}

public BigInteger getFibNumberAtIndex(final int index) {

  if (!memoize.containsKey(index))
    memoize.put(index, getFibNumberAtIndex(index - 1).add(getFibNumberAtIndex(index - 2)));

  return memoize.get(index);
  }
}

Answer 1

这个递归会很快溢出堆栈。这是因为您一遍又一遍地计算较低的斐波那契数 - 指数级的多次。

避免这种情况的一种有效方法是使用内存递归(一种动态编程方法)

基本上使用静态数组来保存已经计算出的斐波那契数，只要需要，就从数组中取出它(如果已经计算过)。如果不是，则计算它并将其存储在数组中。这样每个数字只会被计算一次。

(当然，你可以使用其他数据结构代替数组，即哈希表)