There is a frog jumping on lily pads labeled with natural numbers. It’s on the 2015th lily pad and can either go one step forward or backwards, except if it at any time is on a lily pad divisible by 6 it has to go forward. How many 15-steps paths are possible?
The problem is very nice and can be solved recursively from a mathematical point of view although that’s not the purpose of this article.
From a programming point of view, it’s a very nice problem to solve recursively.
def solver(n, start):
if n == 0:
return 1
else:
if start % 6 == 0:
return solver(n-1, start+1)
else:
return solver(n-1, start+1) + solver(n-1, start-1)
print(solver(15, 2015))
The 0 modulo 6 condition can be implemented as shown above.