Java递归方法计算街道的路径

Question

这只可以向东和向南行驶。例如，向东1个街区，向南2个街区，那么它的总路径为:东 1 个街区和南 2 个街区，向东 1 个街区，然后向南 2 个街区向南 1 个街区，然后向东 1 个街区，然后向南 1 个街区向南 2 个街区，然后向东 1 个街区

向东 6 个街区，向南 6 个街区怎么样？

我的代码是:

public class Path{
    public static int numPaths(int east, int south){

        if( (east==1)&&(south==1)){
            return 2;
        }
        if ((east==1)&&(south==2)){
            return 3;
        }
        else{
        return (numPaths(east,south-1)+numPaths(south-1,east));
        }

    }
    public static void main(String[] args) {
        System.out.println(numPaths(6,6));
    }
}

(但是这不起作用，它在 METHOD 的最后一行提示我的代码，我只是不知道如何修复它。)我想知道原因，而不是答案。

Answer 1

首先，您确实应该使用 else if 将 if 链接在一起。

然而，真正的问题是你没有任何检查来确保值永远不会低于 1。因此，你会得到越来越小的值的无限递归。

添加一个 if block 来检查:

if ((east==1) && (south==1)){
    return 2;
} else if ((east==1) && (south==2)){
    return 3;
} else if ((east==0) || (south==0)) {
    return 0;
} else {
    return (numPaths(east,south-1)+numPaths(south-1,east));
}