I have a tree with node values ( i , j ) where i , j < 1. The children of each node take on the values (i - 1, j), (i - 1, j - 1), and (i, j - 1) respectively. Now, i and j have constraints where they cannot be less than zero, so, given i (or j WLOG) == 0 for a node, its only child becomes (0, j - 1) (assuming j > 0).
These nodes represent the indices of a matrix, and what the children represent are either the index to the West, the North, or the North West of the currently selected index. (Notice 0 either represents the West edge or the North edge of the matrix)
I have written a recursive algorithm that will produce the number of different directions you can walk to get from node_0 (i, j) to the beginning.
def backtrackrecursion( currentnode, counter ): if currentnode.getindex() == (0 , 0): return counter++ if currentnode.geti() > 0: currentnode.addchild(Node(index=(i - 1, j))) if currentnode.getj() > 0: currentnode.addchild(Node(index=(i, j - 1))) if currentnode.getindex() >= ( 1 , 1 ): currentnode.addchild(Node(index=(i - 1, j - 1))) for child in currentnode.getchildren(): counter += backtrackrecursion(child, counter) return counter
I understand why this works. My girlfriend wrote another algorithm, and to my astonishment, it works as well.
def btr(cnode, cou): if cnode.getindex() == ( 0 , 0 ): return cou++ if cnode.getindex() != (0 , 0): cou = btr(cnode.inddecr( -1, 0), cou) + btr(cnode.inddecr(0, -1), cou) + btr(cnode.inddrec( -1 , -1 ), cou) return cou
now I might have missed a property in her class that deletes all children with index i or j < 0, but shouldn't this be an infinite call? Where is the logic that I am missing?