为什么相同的函数用不同的方式写成会有不同的结果呢?

Question

我一直在使用wolfram语言，并注意到一些事情:以不同方式编写的相同函数在时间上的工作方式非常不同。

考虑以下两个函数:

NthFibonacci[num_] := 
 If [num == 0 || num == 1, Return[ 1], 
   Return[NthFibonacci[num - 1] + NthFibonacci[num - 2]]
 ]
Fibn[num_] := {
 a = 1; 
 b =  1; 
 For[i = 0, i < num  - 1, i++,
  c = a + b;
  a = b;
  b = c;
  ];
 Return [b];
 }

NthFibonacci[30]的计算时间约为5秒。
Fibn[900 000]也需要大约5秒来计算。
内置的Fibonacci[50 000 000]

也是如此

我简直不明白为什么这三个人在速度上有这么大的差异。理论上，递归应该或多或少等同于for循环。是什么导致了这种情况?

Answer 1

这是因为您提供的递归版本进行了大量的重复计算。构建一个函数调用树来理解我的意思。即使对于像4这样小的参数，也要查看在逻辑的每个链上生成多少个函数调用来获得基本情况。

                 f(1)
                /
            f(2)
           /    
       f(3)      f(0)
      /    
     /      f(1)
    /
f(4)
    
           f(1)
          /
       f(2)
           
            f(0)

使用递归，函数调用的数量随着参数num呈指数增长。

相比之下，循环版本在num中线性增长。在n 比2ⁿ少工作之前，n的值不会很大。

Answer 2

实现递归的方法有很多;斐波那契函数就是一个很好的例子。正如pjs已经指出的那样，经典的双递归定义呈指数级增长。基数是

φ = (sqrt(5)+1)/2 = 1.618+

你的NthFibonacci实现就是这样工作的。它的阶是φ^n，这意味着对于较大的n，调用f(n+1)所需的时间是f(n)的φ倍。

更温和的方法在执行流中只计算每个函数值一次。而不是指数时间，它需要线性时间，这意味着调用f(2n)需要的时间是f(n)的2倍。

还有其他方法。例如，动态规划(DP)保留了先前结果的缓存。在pjs f(4)的情况下，DP实现只计算f(2)一次;第二个调用将看到第一个调用的结果在缓存中，并返回结果，而不是进一步调用f(0)和f(1)。这趋向于线性时间。

也有创建检查点的实现，例如缓存f(k)和f(k)+1，因为k可以被1000整除。这些方法可以节省时间，因为它们的起始点不会比期望的值低太多，给它们998次迭代的上限来找到所需的值。

最终，最快的实现使用直接计算(至少对于较大的数字)，并且在常量时间内工作。

φ = (1+sqrt(5)) / 2 = 1.618...
ψ = (1-sqrt(5)) / 2 = -.618...
f(n) = (φ^n - ψ^n) / sqrt(5)

Answer 3

通过让递归函数记住先前的值，可以在一定程度上解决@pjs注意到的问题。(去掉If也有帮助)

Clear[NthFibonacci]
NthFibonacci[0] = 1
NthFibonacci[1] = 1
NthFibonacci[num_] := 
 NthFibonacci[num] = NthFibonacci[num - 1] + NthFibonacci[num - 2]
NthFibonacci[300] // AbsoluteTiming

{0.00201479, 3.59 10^62}

也清理你的循环版本(你几乎不应该在mathematica中使用Return):

Fibn[num_] := Module[{a = 1, b = 1,c},
  Do[c = a + b; a = b; b = c, {num - 1}]; b]
Fibn[300] // AbsoluteTiming

{0.000522175,3.59 10^62}

你会发现递归形式会慢一些，但并不可怕。(注意递归形式也会达到1000左右的深度限制)