recursion - OCaml 评估期间的堆栈溢出

Question

我在实现 Heron of Alexandria 的平方根近似算法时遇到堆栈溢出问题，给出如下:

We start with an initial (poor) approximate answer that the square root is 1.0 and then continue improving the guess until we're within delta of the real answer. The improvement is achieved by averaging the current guess with x/guess. The answer is accurate to within 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(循环递归？)。 错误。我尝试在 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-normal form s)

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

^{(这可能更具可读性，有些人使用像guess'这样的名字)}

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

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

^{(没有递归，但是lexical scoping)}

但我不喜欢那样编码(重用相同名称guess)

根据经验，不要羞于使用括号(或 begin ... end 这是相同的)和中间 let 绑定(bind)。两者都使您的代码更具可读性。