在OCaml评估过程中发生堆栈溢出

Question

当我尝试实现亚历山大·海伦的平方根逼近算法时，遇到了堆栈溢出问题，该算法如下：

我们从一个初始（较差）的近似答案开始，即平方根为1.0，然后继续改进猜测，直到我们与实际答案的差距小于delta。通过将当前猜测值与x / guess取平均值来实现改进。答案的精度在delta = 0.0001以内。

我的实现尝试如下：

let squareRoot (x : float) : float =
  let rec aux input guess =
    if abs_float(guess**2. -. input) < 0.0001 then guess
    else aux input (guess +. input/.guess)/.2. in
  aux x 1.;;

然而，这会在OCaml REPL中引发一个# Stack overflow during evaluation (looping recursion?).错误。我尝试用Python实现相同的算法如下：

def squareRoot(x):
  def aux (s, guess):
    if abs(pow(guess,2) - s) < 0.0001:
      return guess
    else:
      return aux (s, (guess + s/guess)/2)
  return aux (x, 1)

......一切都很顺利。于是我开始尝试修改OCaml代码，将我的原始尝试改为：

let squareRoot (x : float) : float =
  let improve i g = (g +. i/.g)/.2. in
  let rec aux input guess =
    if abs_float(guess ** 2. -. input) < 0.0001 then guess
    else aux input (improve input guess) in
  aux x 1.;;

我所做的改变只是将算法改进部分包装在一个单独的函数中，但现在代码可以成功运行，没有任何堆栈溢出错误！

如果有人能解释为什么会这样，以及 OCaml REPL/编译器可能不会在我的第一次迭代代码中识别递归调用中的终止条件等机制，我将不胜感激。

- user5835083

---

你可以添加一些调试 Printf.eprintf 或使用 Ocaml 调试器。 - Basile Starynkevitch

@BasileStarynkevitch 感谢您的建议！我只是玩了几天OCaml，如果这个问题太简单了，对不起。 - user5835083

Answer 1

aux input (guess +. input/.guess)/.2. 

^{(aux的应用发生在除以2之前。...)}

被解析为

  (aux input (guess +. input/.guess))/.2

---

你真的想要

  aux input ((guess +. input/.guess)/.2.)

甚至可以（阅读关于A-正则形式的内容）

  let newguess = (guess +. input/.guess)/.2. 
  in
      aux input newguess

^{(这可能更易读，一些人使用类似 guess' 的名称)}

顺便说一下，有些人会编写以下代码

  let guess =  aux input ((guess +. input/.guess)/.2.)
  in aux input guess

^{（没有递归，但有词法作用域）}

但我不喜欢那样编码（重复使用相同的名称guess）

通常来说，不要害羞地使用括号（或者相同的begin ... end），以及中间的let绑定。这两种方法使您的代码更易读。

- Basile Starynkevitch

---

这只是一个简单的语义错误，我还以为有更大的背景故事呢... /facepalm 非常感谢！ - user5835083