1

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:
        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?

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

1 Answer 1

-2

If i and j have to be less then one but not less then zero then no recursion is possible because if 0<=i<1 and 0<=j<1 then i-1<0 and j-1<0, so no new nodes can appear.

4
  • 1
    This would be a better answer if you made it a complete explanation, rather than an out-of-context response to something the OP said. In other words, this reads more like a comment than it does an answer. Commented Feb 21, 2015 at 18:35
  • He asked why it is not an infinite call and I answered it, what exactly is wrong?
    – k-l
    Commented Feb 22, 2015 at 1:40
  • You're just going to focus on the last 10 words of his question? Commented Feb 22, 2015 at 1:41
  • Maybe I am missing something, what exactly is 71666 asking?
    – k-l
    Commented Feb 22, 2015 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.