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包来自动“记忆”返回值。这是 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 个计算值都已经缓存并且可以返回。