如何在 Python 中创建递归平方根? [英] How can I make a recursive square root in Python?

问题描述

我有这个代码:

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

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

Why? And it doesn't work with other square roots...

推荐答案

看起来您正在尝试实施 除法 计算平方根的算法(虽然我真的不知道)；不过，我不确定您为什么要使用内置的幂运算符 (**)，但您不应该这样做.

It looks like you're attempting to implement the divided differences algorithm for computing square roots (I can't really tell, though); I'm not sure why you use the built in power operator (**) in this, though - you shouldn't be.

递归平方根的基本策略是猜测平方根，检查猜测的准确性，如果旧的猜测不够准确，则创建一个新的猜测，并继续递归下去，直到猜测足够接近真正的根返回.

The basic strategy for a recursive square root is to guess the square root, check the guess's accuracy, create a new guess if the old one isn't accurate enough, and continue doing so recursively until the guess is close enough to the true root to return.

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

In order to control the accuracy of the result (and the depth of the recursion), we need to be able to check our guess against the actual square root; we can do this by squaring it and making the difference between it and the number we're finding the square root of very small.

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

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

In order to actually find the square root, we need a method of arriving at a better guess; this is where the algorithm comes in. I choose to use Newton's method because it's fairly simple.

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

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

Now we can put it all together:

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

我们可以再多一步消除猜测参数:

And we can eliminate the guess parameter with one more step:

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

这篇关于如何在 Python 中创建递归平方根?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！