recursion - 在OCaml中评估期间堆栈溢出

在实现亚历山大·赫伦的平方根逼近算法时，遇到了堆栈溢出问题，如下所示:

我们从平方根为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 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 /编译器背后的机制可能无法识别递归调用中的终止条件，我将不胜感激。

最佳答案

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

(aux的应用发生在被2.除以...之前)

被解析为

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

你真的要

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

甚至(了解A-normal form)

  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绑定。两者都使您的代码更具可读性。