递归为什么我的递归循环打印相同的值两次？JAVA

Question

下面的代码递归地将x减少1，直到它等于y。它打印一个表示递归过程的字符串。 我不希望在字符串中打印x的起始值

private static String createPath(int x, int y, String path) {
        if (x > y) {
            path += "(" + (x-1) + "," + y + ") ";
            return createPath(x - 1, y, path);
        }
        else 
            return path += "(" + x + "," + y + ") ";
    }

当我输入以下内容时：

System.out.println(createPath(5, 1, ""));

我得到以下输出：

(4,1) (3,1) (2,1) (1,1) (1,1) 

为什么最终值（1,1）要打印两次？我注意到当我从

path += "(" + (x-1) + "," + y + ") ";

输出变为：

(5,1) (4,1) (3,1) (2,1) (1,1)

但再一次，我不希望（5，1）被打印在字符串中。此外，我也看过Why is my recursive loop printing the last value twice at the end?，但它似乎对我没有帮助

Answer 1

正确的解决方案：

    private static String createPath(int x, int y, String path) {
        if (x > (y + 1))
            return createPath(x - 1, y, path + "(" + (x - 1) + "," + y + ") ");
        else 
            return path + "(" + (x - 1) + "," + y + ") ";
    }

注意，if (x > (y + 1))和(x - 1)在else分支中

函数的执行顺序如下所示：

createPath(5, 1) => createPath(4, 1, "(4,1)");
createPath(4, 1) => createPath(3, 1, "(3,1)");
createPath(3, 1) => createPath(2, 1, "(2,1)");
createPath(2, 1) => createPath(1, 1, "(1,1)");
// and the last one in the else branch
createPath(1, 1) => createPath(1, 1, "(1,1)");

正如您所看到的，您需要在else分支中添加（x-1），并修改if语句，以使您能够更早地到达else分支，以防止它低于1

Answer 2

您的定义应如下所示：

private static String createPath(int x, int y, String path) {
    if (x <= y) {
        return path;
    }
    path += "(" + (x - 1) + "," + y + ") ";
    return createPath(x - 1, y, path);
}

此定义将确保x <= y一经返回path的值

Answer 3

仅仅因为当x==2和y==1条件x>y为真并且"(" + (x-1) + "," + y + ") "返回（1,1）

Answer 4

结果表明，最终值被打印两次的原因是else返回语句不必要地添加了（x，y）的最终值。比如说,

else 
      return path += "(" + x + "," + y + ") ";

上述代码在x不再大于y时执行，这意味着通过createPath(int x, int y, String path)的路径值包含彼此相等的（x，y）。然而，上面的else语句所做的是再次将x和y的值添加到path，此时需要做的只是return path;