我可以修复此递归函数以使调用不深吗？

Question

我正在学习 R 的 class，我被要求实现牛顿平方根法。我以前做过这个，但是在使用尾递归的函数式语言中，堆栈不会填满，因为数学是在每次递归调用时完成的，而不是在回调上完成的。

我实现了功能。但是我得到： 'Error: C stack usage 15924912 is too close to the limit' 当我将该函数应用于非常大的数字时。我想知道是否可以修改我的功能来解决这个问题。

my_sqr <- function(number, sqrt_guess = 1) {
  if (abs((number/sqrt_guess) - sqrt_guess) < .001) sqrt_guess
  else my_sqr(number, improve_guess(number,sqrt_guess))
}

improve_guess <- function(number, guess) {
  return ((guess + (number/guess)) / 2)
}

# test your script on few examples here, example
# Note I will use the results in check1, check2, check3 to grade your sqrt function
# my_test1 <- my_sqr(16)
# my_test2 <- my_sqr(25)
# my_test3 <- my_sqr(400)
# my_test4 <-my_sqr(5000000000000000)
check1 <- my_sqr(2)
check2 <- my_sqr(1e-60)
check3 <- my_sqr(1e+60)

除最后一次调用 "my_sqr(1e+60)" 外，该函数适用于所有测试。这是我收到错误的地方。

Answer 1

该错误会阻止您进入永无止境的循环。您可以改用此函数，但是使用 1e+56 或更高版本可能永远不会结束...

#here you can see those limits
Cstack_info()

#here is the code

library(rbenchmark)  

new_my_sqr <- function(number, sqrt_guess = 1) {
    while (abs((number/sqrt_guess) - sqrt_guess) > .001) {
        sqrt_guess <- ((sqrt_guess + (number/sqrt_guess)) / 2)
    }
    return (sqrt_guess)
}

#You can compare execution time with something like this...

benchmark("See the change in time from 1e+55..." = {check3x1 <- new_my_sqr(1e+55)},
          "...to 1e+56" = {check3x2 <- new_my_sqr(1e+56)},
          replications = 2,
          columns = c("test", "replications", "elapsed")
)

Answer 2

跟进@CésarArquero 的回答，就 "avoiding recursion" 部分而言，这很好，但实际上并没有解决问题的根源 - 这是浮点不精确。这些问题可能会影响递归和非递归实现：您要么需要（1）重新表述问题以避免不精确；要么(2) 设置最大迭代次数以避免无限循环结果；或 (3) 使用更高精度的算法（例如 library("Rmpfr") - 虽然这通常是最后的手段）。

如下所示，对于算法不会进入无限循环的大值，它需要 <500 次迭代，因此在 1447 次迭代时崩溃（评论中提到由上面的@RuiBarradas 提供）可能来自无限循环。

这是@CésarArquero 函数的增强版本，它设置最大迭代次数并打印出进度信息：

new_my_sqr <- function(number, sqrt_guess = 1, maxit = 10000, tol = 0.001) {
    it <- 0
    dval <- abs((number/sqrt_guess) - sqrt_guess)
    while (it < maxit &&  dval > tol ) {
        sqrt_guess <- (sqrt_guess + number/sqrt_guess) / 2
        dval <- abs((number/sqrt_guess) - sqrt_guess)
        it <- it + 1
        cat(it, sqrt_guess, dval, "\n")
    }
    return (sqrt_guess)
 }

对于 100，一切看起来都很合理 - 猜测与答案的距离平滑地收敛到公差。

new_my_sqr(100)
## 1 50.5 48.5198 
## 2 26.2401 22.42914 
## 3 15.02553 8.370191 
## 4 10.84043 1.615712 
## 5 10.03258 0.06505123 
## 6 10.00005 0.000105791

如果我们使用更大的参数（尽管我们仍然得到正确答案），事情看起来会更有问题：

new_my_sqr(1e30)
## ...
## 51 1.022386e+15 4.428175e+13 
## 52 1.000245e+15 490098151072 
## 53 1e+15 60049048 
## 54 1e+15 1 
## 55 1e+15 0

同样...

new_my_sqr(1e54)
## 90 1.183618e+27 3.387511e+26 
## 91 1.014243e+27 2.828522e+25 
## 92 1.0001e+27 1.999934e+23 
## 93 1e+27 9.999345e+18 
## 94 1e+27 0

在 1e54 和 1e56 之间的某个地方，我们切换到一个无限循环（或者如果我没有施加最大迭代次数，那将是无限循环）。

new_my_sqr(1e56)
## 9997 1e+28 2.199023e+12 
## 9998 1e+28 2.199023e+12 
## 9999 1e+28 2.199023e+12 
## 10000 1e+28 2.199023e+12

我还没有花时间弄清楚数值下溢问题是如何工作的：一般的想法是，如果我们尝试 add/subtract 非常不同的量级，我们就会下溢。特别是，sqrt_guess + number/sqrt_guess 与 1 + number/(sqrt_guess^2) 成正比，因此如果我们最终到达 number/(sqrt_guess^2) 非常小的点，我们将遭受灾难性的精度损失。

我做了一些数值实验；我们不会总是陷入循环。

我可以修复此递归函数以使调用不深吗？

Can I fix this recursive function so that the calls aren't deep?

stack-overflow

recursion

r