# Why does this recursion method work? I have explored it for a day or two, and I cannot figure out why

Problem Statement:

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:
if currentnode.getj() > 0:
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?

• Do a test: what does her cnode.inddecr (-1, -1) return for node (1,0)? what about cnode.inddecr (0, -1) on (1,0)? Commented Feb 21, 2015 at 18:29
• Im going to do the test tonight when I see her. Thank you for the brilliant idea. Commented Feb 22, 2015 at 7:21