RecursiveTask是如何计算斐波那契数的？

Question

我正在看RecursiveTask计算斐波那契数的经典例子。我添加了一些输出:参见http://jboston.net/2017/FibonacciOutp.txt，代码如下

仍然不能理解这是如何工作的，为什么我们首先看到所有数字从12开始递减，然后重复多次

计算fcal1.join()=1 number=2 ()=0

计算fcal1.join()=1 number=3 ()=1

代码：

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

public class RecursiveTaskDemo {
public static void main(String[] args) {
    FibonacciCal fibonacciCal = new FibonacciCal(12);
    ForkJoinPool pool = new ForkJoinPool();
    int i = pool.invoke(fibonacciCal);
    System.out.println(i);
}
}

class FibonacciCal extends RecursiveTask<Integer> {
private static final long serialVersionUID = 1L;
final int num;

FibonacciCal(int num) {
    this.num = num;
}

@Override
protected Integer compute() {
    if (num <= 1) {
        return num;
    }
    System.out.println("number=" + num);
    FibonacciCal fcal1 = new FibonacciCal(num - 1);
    fcal1.fork();
    FibonacciCal fcal2 = new FibonacciCal(num - 2);
    int fcal1Join = fcal1.join();
    int fcal2Compute = fcal2.compute();
    System.out.println("number=" + num + " fcal1.join()=" + fcal1Join + " fcal2.compute()=" + fcal2Compute);
    return fcal2Compute + fcal1Join;
}

}

Answer 1

当FibonacciCal::compute被调用时，它派生出一个线程来计算fib(n - 1)，并在启动线程中计算fib(n - 2)。分支看起来有点像这样(fib(n)代表一个运行FibonacciCal(n).compute()的线程)：

STARTING WITH pool.invoke(new FibonacciCal(5)):
fib(5)
A BIT LATER:
fib(5) === fib(3) // The fibcal2.compute() call, printing num = 3
       \== fib(4) // The fibcal1.fork() call, printing num = 4
LATER:
fib(5) === fib(3) === fib(1) // These fib(0/1)s are base cases and will start folding the tree back up
       |          \== fib(2) === fib(0) // Will return 1 and not fork
       |                     \== fib(1) // Will return 1 and not fork
       \== fib(4) === fib(2) === fib(0)
                  |          \== fib(1)
                  \== fib(3) === fib(1)
                             \== fib(2) === fib(0)
                                        \== fib(1)
METHODS START RETURNING:
fib(5) === fib(3) === 1
       |          \== fib(2) === 1
       |                     \== 1
       \== fib(4) === fib(2) === 1
                  |          \== 1
                  \== fib(3) === 1
                             \== fib(2) === 1
                                        \== 1
ADDITIONS START HAPPENING:
fib(5) === fib(3) === 1
       |          \== (1 + 1) = 2 // When a thread joins its child, it prints out its number again.
       |                          // Since the tree is now folding instead of unfolding, the printlns appear, approximately, the opposite order
       \== fib(4) === (1 + 1) = 2
                  \== fib(3) === 1
                             \== (1 + 1) = 2
LATER:
fib(5) === (1 + 2) = 3 === 1
       |               \== 2
       \== fib(4) === 2
                  \== (1 + 2) = 3 === 1
                                  \== 2
END:
8 === 3 === 1
  |     \== 2
  \== 5 === 2
        \== 3 === 1
              \== 2

你得到大量重复数字的原因是因为没有任何记忆。在这个使用fib(5)的示例中，您可以看到8个fib(0)或fib(1)基本术语、3个fib(2)术语、2个fib(3)术语和一个fib(4)。当低阶项开始加入它们的子项时，你会得到许多带有小nums的println，直到末尾到来，它们开始重新计数。