在开始学习lisp时,我遇到了尾递归这个术语.这究竟是什么意思？
language-agnostic algorithm recursion functional-programming tail-recursion
主要问题:我将尾部调用优化(TCO)的最重要应用视为递归调用到循环的转换(在递归调用具有某种形式的情况下).更准确地说,当翻译成机器语言时,这通常会转换成某种跳跃系列.编译为本机代码(例如SBCL)的一些Common Lisp和Scheme编译器可以识别尾递归代码并执行此转换.基于JVM的Lisp(例如Clojure和ABCL)在执行此操作时遇到了麻烦.JVM作为一台可以防止或使其变得困难的机器是什么？我不明白.JVM显然没有循环问题.编译器必须弄清楚如何进行TCO,而不是编译它的机器.
相关问题:Clojure 可以将看似递归的代码转换成循环:如果程序员用关键字替换对函数的尾调用,它就好像它正在执行TCO一样recur.但是,如果有可能让编译器识别尾调用 - 例如SBCL和CCL那样做 - 那么为什么Clojure编译器不能确定它应该按照它处理的方式处理尾调用recur呢？
(对不起 - 这无疑是一个常见问题解答,我确信上面的评论显示了我的无知,但我找不到早期的问题是不成功的.)
Quicksort通常被描述为原位(就地)算法,尽管它需要O(log n)堆栈空间.所以,做原地意味着"需要小于O(n)的额外空间",还是栈空间一般不能算作空间复杂度(但为什么会这样呢？),或者是快速排序实际上不是原地算法？
algorithm complexity-theory terminology quicksort space-complexity