Как создать рекурсивный квадратный корень в python 3.3?

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

Похоже, вы пытаетесь реализовать алгоритм divided differences для вычисления квадратных корней (я не могу сказать, хотя); Я не уверен, почему вы используете встроенный силовой оператор (**) в этом, но не должно быть.

Основная стратегия рекурсивного квадратного корня состоит в том, чтобы угадать квадратный корень, проверить точность угадывания, создать новое предположение, если старое недостаточно точное и продолжать делать это рекурсивно, пока предположение не будет достаточно близко к истинный корень для возврата.

Чтобы контролировать точность результата (и глубину рекурсии), мы должны иметь возможность проверить наше предположение против фактического квадратного корня; мы можем сделать это, возведя в квадрат и сделав разницу между ним и числом, которое мы находим, квадратный корень очень маленький.

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

Для того, чтобы найти квадратный корень, нам нужен способ получения лучшего предположения; это то место, где входит алгоритм. Я выбираю использовать Newton's method, потому что это довольно просто.

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) 

И мы можем исключить параметр догадку с еще один шаг:

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