[SOLVED] Cse2050 homework 05: recursion/dynamic programming

Many of the problems used to teach recursion are not efficiently solved with recursion – summing numbers, finding fibonaccis, and calculating factorials all have elegant but inefficient recursive solutions.

Here, we look at a problem type where recursive solutions tend to be genuinely useful: exploring branching paths until we hit a dead end or find a solution. We’ll see this a lot in graphs later this semester, and it often comes up when modelling games.

The basic problem abstraction is this:

Stepping Game:

We will model a circular board game. The board consists of a series of tiles with numbers on them.

Not all boards will be solvable. See provided examples for a solveable and an unsolveable puzzle.

Tips:

def solve_puzzle(L, visited=None): # No helper function

if visited is None: # initialize

# the rest of your work here

def solve_puzzle(L): # Using a helper function

visited = set()

return _solve_puzzle(L, visited)

def _solve_puzzle(L, visited):

# the rest of your work here

Submission:

At a minimum, submit the following files: