Teaching Kids Programming – Estimate the Math Continued Fraction Value in Python (Recursion and Iterative Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Let’s take a look at this golden ratio continued fraction:

continued-fraction-golden-ratio

We can see the pattern is recursive (infinitely) and thus we can replace portion of the expression with itself:

continued-fraction-math

Thus:

So we have a positive root:
which is the golden ratio.

Similarly, if the continued fraction is [2:2,2,2,2,2….], the value is

We can use the values from both to estimate the value of and by evaluating the continued fraction.

We can implement the continued fraction using the following Python code (Recursive manner). The parameter n is the number of the iterations to go. Beware that when n is large, the Recursion may be causing stack-over-flow if compiler hasn’t been able to tail optimise it.

def continuedFraction(n, a):
    if n == 0:
        return a / (a + a/a)
    return a / (a + continuedFraction(n - 1, a))

We can also do this iteratively (and in practice more efficient than the Recursive version):

def continuedFraction(n, a):
    ans = 0
    for _ in range(n):
        ans = a / (a + ans)
    return ans

–EOF (The Ultimate Computing & Technology Blog) —