Dynamic solution to the frog problem.

frog.py

####################
# Can you solve the frog problem?
# Regarding the video: https://www.youtube.com/watch?v=ZLTyX4zL2Fc
# By: Aaron Mader
# 
# Note: This code doesn't actually NEED to be recursive, you could just iterate your way up from 1 to n. 
# But your fractions will get pretty large (around n=500) before you run out of recursion depth 
# (which happens at n=1000), so it doesn't really matter.
####################

from fractions import Fraction

cache = {}

def fn(n):
    # with n spaces remaining, what's my number of hops to get there?
    # if n == 1:
    #     return 1
    # if n == 2:
    #     return 1/2 + 1/2 (fn(1)+1)
    # if n == 3:
    #     return 1/3 + 1/3 (fn(2)+1) + 1/3 (fn(1)+1)
    # ...
    if n in cache:
        return cache[n]

    # factor = 1.0/n
    factor = Fraction(1,n)

    num_hops = factor
    for i in range(1, n):
        num_hops += factor * (fn(n-i) + 1)

    cache[n] = num_hops
    return num_hops

n = 10
result = fn(n)
print "expected number of hops for n={0} is {1}".format(n, result)