clojure recur vs命令循环

Question

学习Clojure并尝试理解实现:

有什么区别:

(def factorial
  (fn [n]
    (loop [cnt n acc 1]
       (if (zero? cnt)
            acc
          (recur (dec cnt) (* acc cnt))
; in loop cnt will take the value (dec cnt)
; and acc will take the value (* acc cnt)
))))

和以下类似C的伪代码

function factorial (n)
    for( cnt = n,  acc = 1) {
        if (cnt==0) return acc;
        cnt = cnt-1;
        acc = acc*cnt;
    }
// in loop cnt will take the value (dec cnt)
// and acc will take the value (* acc cnt)

clojure的"循环"和"复发"是专门设计用于编写简单的命令循环的形式吗？(假设伪代码的"for"创建了它自己的范围,因此cnt和acc仅存在于循环内)

Answer 1

Clojure loop和recur表单是否专门用于编写简单的命令循环？

是.

在功能方面:

• 循环是一种简并形式的递归,称为尾递归.
• '变量'不会在循环体中修改.相反,只要重新进入循环,它们就会被重新化身.

Clojure recur对周围的递归点进行尾递归调用.

• 它重新使用一个堆栈帧,因此工作速度更快,避免堆栈溢出.
• 它只能作为任何调用中的最后一件事 - 在所谓的尾部位置.

每次连续recur调用都会覆盖最后一次,而不是堆叠起来.

递归点是

• 一fn形式中,在可能的伪装defn或letfnOR
• 一个loop表单,它还绑定/设置/初始化本地/变量.

所以你的factorial功能可以重写

(def factorial
  (fn [n]
    ((fn fact [cnt acc]
      (if (zero? cnt)
        acc
        (fact (dec cnt) (* acc cnt))))
     n 1)))

...哪个更慢,并且存在堆栈溢出的风险.

并非每个C/C++循环都能平滑转换.您可以从嵌套循环中遇到麻烦,其中内部循环修改外部循环中的变量.

顺便说一下,你的factorial功能

• 会很快导致整数溢出.如果你想避免这种情况,请使用1.0而不是1获得浮点(双)算术,或者使用*'而不是*获得Clojure的BigInt 算术.
• 将在负面论证上无休止地循环.

对后者的快速解决方法是

(def factorial
  (fn [n]
    (loop [cnt n acc 1]
      (if (pos? cnt)
        (recur (dec cnt) (* acc cnt))
        acc))))
; 1

......虽然返回nil或更好Double.NEGATIVE_INFINITY.

Answer 2

查看loop/的一种方法recur是,它允许您编写功能正常的代码,但底层实现最终基本上是一个命令性循环.

要看到它的功能,请举个例子

(def factorial
  (fn [n]
    (loop [cnt n acc 1]
      (if (zero? cnt)
        acc
        (recur (dec cnt) (* acc cnt))))))

并重写它,以便将loop表单分解为单独的帮助函数:

(def factorial-helper
  (fn [cnt acc]
    (if (zero? cnt)
      acc
      (recur (dec cnt) (* acc cnt)))))

(def factorial'
  (fn [n]
    (factorial-helper n 1)))

现在您可以看到辅助函数只是调用自身; 你可以recur用函数名替换:

(def factorial-helper
  (fn [cnt acc]
    (if (zero? cnt)
      acc
      (factorial-helper (dec cnt) (* acc cnt)))))

您可以查看recur,当用于factorial-helper简单地进行递归调用时,由底层实现进行优化.

我认为一个重要的想法是,它允许底层实现成为命令式循环,但您的Clojure代码仍然可以正常运行.换句话说,它不是一个允许你编写涉及任意赋值的命令循环的结构.但是,如果以这种方式构建功能代码,则可以获得与命令式循环相关的性能优势.

将命令性循环成功转换为此形式的一种方法是将命令式赋值更改为"分配给"递归调用的参数参数的表达式.但是,当然,如果遇到一个执行任意赋值的命令循环,您可能无法将其转换为此形式.在这个视图中,loop/ recur是一个更受约束的结构.