python - 如何在 Python 中创建递归平方根？

Question

我有这个代码：

def root(x,n):    
    if n==0:
        return x
    else:
        return 0.5**(x/root(x,n-1)+root(x,n-1))

但：

>>>root(4,2)
>>>2.05

为什么？它不适用于其他平方根...

Answer 1

看起来您正在尝试实现用于计算平方根的除差算法（不过我无法确定）；不过，我不确定您为什么在此使用内置的幂运算符（**）-您不应该这样做。

递归平方根的基本策略是猜测平方根，检查猜测的准确性，如果旧的猜测不够准确，则创建一个新的猜测，然后递归地继续这样做，直到猜测足够接近真根返回。

为了控制结果的准确性（以及递归的深度），我们需要能够根据实际平方根来检查我们的猜测；我们可以通过对其进行平方并将其与我们找到的平方根的数字之间的差异来做到这一点非常小。

def goodEnough(guess, x):
    return abs((x - (guess * guess))) <= .01 #change this value to make the function more or less accurate

为了真正找到平方根，我们需要一种更好的猜测方法；这就是算法的用武之地。我选择使用牛顿法，因为它相当简单。

def newGuess(guess, x):
    return (guess + guess/x)/2

现在我们可以把它们放在一起：

def root(guess, x):
    if goodEnough(guess, x):
        return guess
    else:
        return root(newGuess(guess, x), x)

我们可以通过多一步消除guess 参数：

def sqrt(x):
    return root(x/2, x) #x/2 is usually somewhat close to the square root of a number

Answer 2

它确实有效，唯一的问题是递归调用的数量越高，即 n 在这种情况下，您的结果应该越准确，因为计算中的错误减少了还确保包括当 n == 0 时的案例计算