java - 尝试从递归方法中删除辅助计数器变量

Question

Project Euler 15(剧透):

我通过意识到它是一个 central binomial coefficients 的序列解决了这个问题。 。另一个好方法是通过dynamic programming 。尽管如此，递归执行似乎很自然，所以我还是这么做了。

这是我的解决方案:

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++;
    }
}

注意:棋盘的大小为:1 + inputSize，因此在本例中为 21，因为我们有一个 20x20 的网格。这是因为解决上述 2x2 问题相当于解决 3x3 问题，但要穿过正方形而不是在其边界上行进。

getPaths(Position p)的逻辑是:尽可能向下走，然后尽可能向右走。一旦到达右下Position，将路径数加 1 (count)，返回到您上次下台阶的位置，现在不再向下，而是向右走(如果不能向右走，则再次原路返回，等等)。重复过程。当然，递归本身正在跟踪所有这些。如果不清楚，或者如果有人想搞乱工作代码，有两个小类 here 。向 getPaths(Position p) 添加一些打印语句应该会让发生的事情变得非常明显。

无论如何，这一切都工作正常，我的问题是如何在不使用 count 的情况下实现这一点。再次，正如我上面所说，我知道有更好的方法来解决这个问题，这不是我的问题。我的问题是尝试获得与上面相同的功能，但不使用辅助变量。这意味着将 getPaths(Position p) 从 void 更改为返回 long。这可能是一个简单的修复，但我现在还没有看到它。提前致谢。

本质上，我希望递归调用它们自己来跟踪计数，而不是任何类型的实际计数器。

Answer 1

我相信这应该有效

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);
}