在正确的尾巴中毒中再次出现

Question

应该在尾部位置调用重现，我假设它实际上充当非递归的准循环。

在下面的模拟块结构中，expr 1或2是否被认为是在正确的尾部位置，而expr 3到8都没有？否则，如何在诉诸线索和错误之前对其进行推理和识别？

(defn foo [x]
 (if cond-expr-1
  (recur expr-1)
  (recur expr-2)))

(defn bar [x]
 (if cond-expr-2
  (fn-1 (recur expr-3))
  (fn-2 (recur expr-4))))

(defn baz [x]
 (if cond-expr-3
  (if cond-expr-4  
    (recur expr-5)
    (recur expr-6))
  (if cond-expr-5  
    (recur expr-7)
    (recur expr-8))))

Answer 1

对于expr-3和expr-4，它是函数的参数，这就是为什么它不在尾部位置的原因。

调用recur基本上就像一个goto或return语句，这两个语句都不能在函数参数列表中使用。

因为if表达式不是一个函数(它是一个“特殊形式”)，所以与函数arg列表一样没有问题。

下面是loop/recur与使用while的一种更命令式方法的比较

(ns tst.demo.core
  (:use tupelo.core tupelo.test))

(defn fib-recur
  [arg]
  (assert (and (int? arg) (pos? arg)))
  ; initialize state vars
  (loop [N      arg
         result 1]
    (if (zero? N)
      result
      ; compute next state vars
      (let [N-next      (dec N)
            result-next (* result N)]
        (recur N-next result-next))))) ; jump to top of loop with next state vars

(defn fib-while
  [arg]
  (assert (and (int? arg) (pos? arg)))
  ; initialize state vars
  (let [state (atom {:N      arg
                     :result 1})]
    (while (pos? (:N @state)) ; must use newest state value for N in test
      ; compute next state vars
      (let [N          (:N @state)
            result     (:result @state)
            state-next {:N      (dec N)
                        :result (* result N)}]
        (reset! state state-next))) ; save new state & jump to top of loop
    (:result @state)))

(dotest
  (is= 120 (fib-recur 5))
  (is= 120 (fib-while 5)))

Answer 2

如果在表达式后面的当前函数中没有其他要计算的内容，则表达式处于尾位置。在您的示例中，foo和baz中的所有baz调用都位于尾位置，因此这两个函数都可以很好地编译。

但是，在bar中，由于expr-3或expr-4都不处于尾部位置，因此不允许任何一个expr-3调用。有些函数调用使用每个recur调用的结果作为参数--也就是说，函数调用在逻辑上遵循recur调用，因此recur不在尾位置。

这并不是说不能编写bar来对自身进行递归调用，而是必须显式地对其进行编码，如下所示：

(defn bar [x]
 (if cond-expr-2
  (fn-1 (bar expr-3))
  (fn-2 (bar expr-4))))

这是绝对允许的，但是这些对bar的递归调用将占用堆栈空间，这意味着如果函数递归地调用自己足够多的时间，您将耗尽堆栈空间。recur (和尾递归)是很有价值的，因为它不需要进行传统意义上的函数调用，而是(在这里逻辑地)将堆栈上的函数参数替换为新的参数，代码跳回函数的开头，因此不使用堆栈空间。当然，这意味着第一个函数调用中的原始参数丢失了。

其他版本的Lisp不使用recur关键字。当Lisp的这些版本发现一个函数正在递归地调用自己时，它们会执行Clojure所做的相同的“尾位置”确定，如果发现调用处于尾位置，则执行相同的“替换-参数-跳转”逻辑Clojure，而如果它们发现调用不在尾位置，则会发出代码来执行“真正的”递归调用，而不是失败编译。Clojure的优势在于，如果将调用编译为尾递归调用(分支)，则对开发人员来说非常明显。