clojure - 如何将 while 循环转换为 clojure 代码

Question

例如扩展欧几里得算法(引自wiki):

function extended_gcd(a, b)
    x := 0    lastx := 1
    y := 1    lasty := 0
    while b ≠ 0
        quotient := a div b
        (a, b) := (b, a mod b)
        (x, lastx) := (lastx - quotient*x, x)
        (y, lasty) := (lasty - quotient*y, y)       
    return (lastx, lasty)

我尝试过并得到:

 (defn extended-gcd 
  [a b]
  (loop [a a b b x 0 y 1 lx 1 ly 0]
     (if (zero? b)
      [lx ly]
      (recur b (mod a b)
             (- lx (* (int (/ a b)) x))
             (- ly (* (int (/ a b)) y))
             x y))))

我想我可以找到一种方法来翻译处理序列的循环。但这个怎么样？我如何以 Clojure 的方式编写它？一些带有map、reduce等的东西而不是循环递归。

Answer 1

对于扩展的欧几里德算法，您可以使用简单的递归，这使得函数看起来非常优雅:

(defn extended-gcd [a b]
  (if (zero? b) [1 0]
    (let [[q r] [(quot a b) (rem a b)]
          [s t] (extended-gcd b r)] 
      [t (- s (* q t))])))

让我们尝试一下:

user=> (extended-gcd 120 23)
[-9 47]

---

并非所有问题都需要通过使用map/reduce/sequence来解决。我认为上面的内容与 Clojure 的方式一样，都是您正在寻找的“(reduce + [1 2 3 4 5])”类型的答案。