loops - Racket expt 是否使用尾递归？

Question

如果我在球拍中尝试这个：

(expt 2 1000)

我得到一个比宇宙中所有原子大很多倍的数字：

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

我什至可以变得更疯狂，(expt 2 10000)在我的 T450 笔记本电脑上仍然只需要一秒钟。据我了解，这仅是因为尾递归才有可能。这个对吗？如果是这样，Racket 的尾递归是纯函数式编程，还是在幕后发生隐藏的副作用？另外，当我看到 Common Lisp'sloop时，它是否基于引擎盖下的尾递归？一般来说，我想我想知道这些递归/循环的壮举是如何实现的。

标签： loopslisprackettail-recursion

Answer 1

Racket 使用 C 库来实现大整数 (bignums)。该库称为 GMP：

https://gmplib.org/manual/Integer-Exponentiation.html

现在 2^n 的情况很容易在二进制表示中实现。您只需要一个 1 后跟 n 个零。也就是说，GMP 可以非常快速地计算数字。