Julia中的递归函数如何工作？

Question

此代码在Julia中：

function seq(n)
       if n<2
           return BigInt(2)
       else
           return 1/(3-seq(n-1))
       end
   end

# and then run
[seq(n) for n=1:10]

复制递归序列Un = 1 /（3-U（n-1）），其中U1 = 2，并且它起作用。但是有人可以向我解释它是如何工作的吗？对于每n个，它都会计算出它之前的每一项，还是将“返回”存储在某个地方，然后在需要时可以再次调用它，这样就不必每次都计算n项了？

Answer 1

这只是一个普通的递归函数：它需要多次调用自身才能计算结果。它终止是因为每个调用链最终都到达了基本情况。没有隐式的结果缓存或类似的东西，无论调用函数多少次，它都会重新计算相同的结果。如果要记住以前计算的值，可以使用Memoize程序包自动“ Memoize”返回值。这是未记忆功能的简短版本：

memoize

我将其更改为适合单行并返回

julia> seq(n) = n < 2 ? BigFloat(2) : 1/(3-seq(n-1))
seq (generic function with 1 method)

julia> seq(1) # trigger compilation
2.0

julia> @time [seq(n) for n=1:100];
  0.001152 seconds (20.00 k allocations: 1.069 MiB)

julia> @time [seq(n) for n=1:100];
  0.001365 seconds (20.00 k allocations: 1.069 MiB)

而不是BigFloat(2)，因为由于除法运算，对于较大的输入，该函数返回BigInt(2)。请注意，第二个时间不会比第一个时间快（事实上，这很慢，因为可能是在第二个时间开始垃圾回收，但不是在第一个时间开始）。这是同一件事，但带有备注：

BigFloat

即使备忘录缓存在开始时是空的，但第一次计时比未记忆的版本要快得多，因为相同的计算已进行了很多次，备忘录避免了第一次以外的所有事情。第二个时间甚至更快，因为现在所有100个计算值都已被缓存并且可以返回。