Trying to remove auxiliary counter variable from recursive method

Question

Project Euler 15 (spoilers): enter image description here

I solved this problem by realizing that it was a sequence of central binomial coefficients. Another good way is through dynamic programming. Nonetheless, it seemed so natural to do recursively, that I did it anyway.

Here's my solution:

public long getNumberOfPaths()
{
    getPaths(board[0][0]); //2D array of Positions
    return count; //instance member (long)
}

private void getPaths(Position p)
{   
    if (p.hasDown())
    {
        getPaths(p.getDown());
    }

    if (p.hasRight())
    {
        getPaths(p.getRight());
    }

    if ((p.getRow() == board.length - 1) && (p.getColumn() == board.length -1))
    {
        count++;
    }
}

NB: Size of board is: 1 + inputSize, so in this case it would be 21, since we have a 20x20 grid. This is because solving the above 2x2 problem is equivalent to solving the 3x3 problem, but going through the squares instead of traveling on their borders.

The logic of getPaths(Position p) is: go down for as long as you can, then go right for as long as you can. Once you hit the bottom right Position, add 1 to number of paths (count), go back to where you last stepped down and now instead of going down, go right instead (if you can't go right, backtrack again, etc). Repeat process. Of course, the recursion itself is keeping track of all of this. If it's not clear, or if anyone want to screw with working code, there are two, small, classes here. Adding a few print statements to getPaths(Position p) should make what's going on pretty obvious.

Anyway, this all works properly, my question is how to implement this without using count. Again, as I stated above, I know that there are better ways to solve this problem, that's not my issue. My issue is trying to get the same functionality as above, but without using an auxiliary variable. This would mean changing getPaths(Position p) from void to making it return a long. It may be a simple fix, but I'm just not seeing it right now. Thanks in advance.

Essentially I want the recursive calls them selves to keep track of the count, not any sort of actual counter.

Zim-Zam O'Pootertoot · Accepted Answer · 2013-06-27 16:37:47Z

1

I believe this should work

private long getPaths(Position p) {
    return (p.hasDown() ? getPaths(p.getDown()) : 0) +
        (p.hasRight() ? getPaths(p.getRight()) : 0) +
        ((p.getRow() == board.length - 1) && (p.getColumn() == board.length -1) ? 1 : 0);
}

answered Jun 27, 2013 at 16:37

Zim-Zam O'Pootertoot

18.2k4 gold badges45 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Zim-Zam O'Pootertoot Over a year ago

@Steve P. That's strange, I don't see where it would be prematurely terminating. Maybe one of my parentheses is incorrectly nested

Zim-Zam O'Pootertoot Over a year ago

@Steve P. Yeah, my parentheses were off at first

darijan · Accepted Answer · 2013-06-27 17:09:30Z

1

Without using the auxiliary variable:

public long getNumberOfPaths()
{
    return getPaths(new Position(0,0)); //2D array of Positions
}

private long getPaths(Position p)
{  
    long result= 0;
    if (p.hasDown())
    {
        result+= getPaths(p.getDown());
    }

    if (p.hasRight())
    {
        result+= getPaths(p.getRight());
    }

    if ((p.getRow() == board.length - 1) && (p.getColumn() == board.length -1))
    {
        result+= 1;
    }
    return result;
}

Try this then:

private long getPaths(Position p)
{ 
    return (p.hasDown() ? getPaths(p.getDown()) : 0) + 
                 (p.hasRight() ? getPaths(p.getRight()) : 0) + 
                 ((p.getRow() == board.length - 1) && 
                 (p.getColumn() == board.length -1) ? 1 : 0);
}

edited Jun 27, 2013 at 17:09

answered Jun 27, 2013 at 16:45

darijan

9,80327 silver badges38 bronze badges

Comments

darijan · Accepted Answer · 2013-06-27 17:06:21Z

0

You could simply change your method signature to keep count as a parameter:

private long getPaths(Position p, long count) {
    if (p.hasDown()) {
        getPaths(p.getDown(), count);
    }

    if (p.hasRight()) {
        getPaths(p.getRight(), count);
    }

    if ((p.getRow() == board.length - 1) && (p.getColumn() == board.length - 1)) {
        count++;
    }
    return count;
}

edited Jun 27, 2013 at 17:06

darijan

9,80327 silver badges38 bronze badges

answered Jun 27, 2013 at 16:38

assylias

330k84 gold badges680 silver badges806 bronze badges

Collectives™ on Stack Overflow

Trying to remove auxiliary counter variable from recursive method

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related