当我尝试实现亚历山大·海伦的平方根逼近算法时,遇到了堆栈溢出问题,该算法如下:
我们从一个初始(较差)的近似答案开始,即平方根为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/编译器可能不会在我的第一次迭代代码中识别递归调用中的终止条件等机制,我将不胜感激。
Printf.eprintf
或使用 Ocaml 调试器。 - Basile Starynkevitch