How can I make a recursive square root in Python?

Question

I've got this code:

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

but:

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

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

Answer 1

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

Answer 2

It does work the only problem is the higher amout of recursive calls i.e n in this case the more accurate your result should be as the error in calculation is reduced also make sure you include the case calculation for when n == 0