代码之家 › 专栏 › 技术社区 › M Dey

我能修正这个递归函数使调用不深吗?

stack-overflow recursion r

M Dey · 技术社区 · 6 年前

我在上一门关于r的课,我被要求实现牛顿平方根法。我以前也这样做过,但在函数语言中使用尾部递归,因为数学是通过每次递归调用而不是回调来完成的,所以堆栈不会填满。

我已经实现了这个功能。但我得到的是:“错误:当我将函数应用于非常大的数字时,C堆栈使用15924912太接近极限”。我想知道是否可以修改我的函数来解决这个问题。

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)”,此函数对每个测试都有效。这就是我犯错误的地方。

0 回复 | 直到 6 年前

César Arquero Cabral 6 年前

那个错误阻止你进入一个永不结束的循环。您可以改用此函数,但是,使用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")
)

Ben Bolker 6 年前

跟进@c_©sararquero的答案,就“避免递归”这一部分而言,这是很好的,但实际上并不能解决问题的根源——浮点不精确。这些问题可能会影响递归和非递归实现:您需要(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

我还没有花时间去弄清楚数值下溢问题是如何工作的:一般的想法是,如果我们试图加上/减去非常不同量级的项,我们将得到下溢。特别地, sqrt_guess + number/sqrt_guess 与 1 + number/(sqrt_guess^2) ,所以如果我们最终 number/(sqrt_guess^2) 是很小的,我们会有灾难性的精度损失。

我做了一些数值实验;我们没有总是陷入循环。