Algorithms
and
Data
Structures

Spring 2022
course
site
-->

README - code/recursion

Examples of recursion.

Once the code for simulating the particular system is set up, the guts of a recursive part is often fairly short. For example, in the peg solitaire code, the search for a solution is

def solve(board):
    """ Search for a solution. Return True if found, 
        leaving board in a solved state. """
    # ... using a recursive backtracking search.
    board.n_positions += 1                 # number of positions examined.
    if board.is_solved():
        return True
    else:
        for move in board.moves:
            if board.can_move(move):
                board.do_move(move)
                if solve(board):           # recursively look at the next position
                    return True
                board.undo_move(move)
    return False

Now we're having fun.