Question 3.py

def nsp(x, y):
    """had to be redone with back tracking although recursion is better down there"""
    trace = [[(0, 0)]]
    sln = []
    while trace:
        current = trace.pop(-1)
        last_position = current[-1]

        if last_position == (x, y):
            sln.append(current)
        else:
            up = (last_position[0] + 1, last_position[1])
            right = (last_position[0], last_position[1] + 1)
            if (up not in current) and ((up[0] <= x) and (up[1] <= y)):
                trace.append(current + [up])
            if (right not in current) and ((right[0] <= x) and (right[1] <= y)):
                trace.append(current + [right])
    return len(sln)


def nsp2(x, y):
    """Same solution but with recursion and shorter"""
    if x < 0 or y < 0:
        return 0
    if (0, 0) == (x, y):
        return 1
    else:
        return nsp2(x, y - 1) + nsp2(x - 1, y)