OCAML评估期间的堆栈溢出

Question

我在Alexandria的Heron实现平方根近似算法时遇到了堆栈溢出问题，如下所示：

我们从平方根为1.0的初始（差）近似答案开始，然后继续改善猜测，直到我们在真实答案的三角洲之内。通过用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替补中引起# 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/编译器背后的机制可能在我的第一次迭代中递归呼叫中未识别终止条件，等等。

Answer 1

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

^{（ aux的应用发生在 2. ...）}

被解析为

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

---

您真的想要

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

甚至（读（阅读a formal形式）

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

^{（可能更可读性，有些人使用guess'之类的名称）}

顺便说一句，有些人会编码

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

^{（没有递归，而是词汇范围）}

但我不喜欢这样的编码（重复使用 same same name guess）

作为经验法则，不要害羞地使用括号（或begin ... end）和中间let绑定。两者都使您的代码更可读。