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.
1 2 3 4 | def continuedFraction(n, a): if n == 0: return a / (a + a/a) return a / (a + continuedFraction(n - 1, a)) |
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):
1 2 3 4 5 | def continuedFraction(n, a): ans = 0 for _ in range(n): ans = a / (a + ans) return ans |
def continuedFraction(n, a):
ans = 0
for _ in range(n):
ans = a / (a + ans)
return ans–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Top Down and Bottom Up Recursive Algorithms to Determine a Balanced Binary Tree
Next Post: Teaching Kids Programming - Clone (Deep Copy) a Undirected Connected Graph using Recursive Depth First Search Algorithm
