Teaching Kids Programming – Recursive Algorithm to Compute the Square Root

Teaching Kids Programming: Videos on Data Structures and Algorithms

We have learned that we can use the binary search algorithm to guess the root – which then converges to the answer we are looking for. We can also use the Recursive algorithm to compute the square root.

Let’s assume the where is the biggest square number that is less or equal to n.
Then, we can rewrite it as:




Recursively replacing the

Thus, we can implement as the following, converging the real root until the Error (EPS) is small enough:

def rSqrt(n, a, EPS = 1e-8):
    b = n - a * a
    x = a + b/a
    t = x
    # while error is still big
    while abs(x*x - n) > EPS:
        x = a + b/(a+t)
        # converge the answer
        t = x
    return x

Test the solution by comparing to Math.sqrt function:

print(rSqrt(150, 12)) # 12.247448713888222
print(sqrt(150))      # 12.24744871391589

This algorithm works for floating numbers as well. This is recursive algorithm however, the implementation is iterative.

–EOF (The Ultimate Computing & Technology Blog) —