function - 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”返回值。这是 unmemoized 函数的简洁版本:

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 由于除法操作，用于更大的输入。请注意，第二个时间并不比第一个快(实际上更慢，可能是因为垃圾收集在第二个而不是第一个期间开始)。这是同样的事情，但带有内存:

julia> using Memoize

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

julia> seqm(1) # trigger compilation
2.0

julia> @time [seqm(n) for n=1:100];
  0.000071 seconds (799 allocations: 36.750 KiB)

julia> @time [seqm(n) for n=1:100];
  0.000011 seconds (201 allocations: 4.000 KiB)

即使内存缓存在开始时是空的，但第一次计时明显快于未内存版本，因为相同的计算进行了多次，内存避免了除了第一次之外的所有操作。第二次计时甚至更快，因为现在所有 100 个计算值都已缓存并且可以直接返回。