c++ - 我在这个递归中哪里错了

Question

先生，这些天我正在提高我的递归技能，但我陷入了“破解编码技能”一书中的递归问题之一。问题编号 8.2
问题陈述是——想象一个机器人坐在 N*N 网格的上角。机器人只能在两个方向上移动:向右和向下。机器人有多少种可能的路径？

我尝试了很多，但它只显示了一条路径。我的代码是(从书的解决方案中获得帮助)

#include<iostream>
#include<vector>

using namespace std;

struct point {
    int x;
    int y;
};
vector<struct point *> v_point;

int findPath(int x, int y) {
    struct point *p = new point;
    p->x = x;
    p->y = y;
    v_point.push_back(p);
    if(x == 0 && y == 0) {
        cout << "\n\t" << x << "  " << y;
        return true;
    }
    int success = 0;
    if( x >= 1 ) {
        cout << "\n success = " << success << " x =  " << x << "  "  << " y = " << y;
        success = findPath(x-1, y);
        cout << "\n success = " << success << " x =  " << x << "  "  << " y = " << y;
    }
    if(!success && y >= 1) {
        cout << "\n\t success = " << success << " x =  " << x << "  "  << " y = " << y;
        success = findPath(x, y-1);
        cout << "\n\t success = " << success << " x =  " << x << "  "  << " y = " << y;
    }
    if(!success){
        cout << "\n\t\t success = " << success << " x =  " << x << "  "  << " y = " << y;
        v_point.pop_back();
        cout << "\n\t\t success = " << success << " x =  " << x << "  "  << " y = " << y;
    }
    return success;
}

main() {
    cout << endl << findPath(3, 3);
    return 0;
}

我用 printf 语句来检查我哪里错了，但我没有发现错误。请帮助我。

我按照您的指示编写了代码。但是，如果我想打印所有路径，它会给出不需要的答案。

int findPath(int x, int y) {
    if(x == 0 && y == 0) { cout << endl; return 1; }
    int path = 0;
    if(x > 0) { cout << "d -> ";path = path + findPath(x-1, y);  } // d = down
    if(y > 0) { cout << "r ->  ";path = path + findPath(x, y-1);  } // r = right
    return path;
}

对于 3*3 的网格，它给出 ( findPaths(2, 2) ) :-

d -> d ->r -> r ->
r -> d -> r ->
r -> d->
r -> d -> d -> r ->
r -> d ->
r -> d -> d ->

Answer 1

您的问题是，当 x >= 1 时，您正在递减 x 并将 success 设置为 true。这可以防止您的代码探索递减 y。

正确的递归规则是:

1. 如果x == 0 && y == 0，返回1(空路径是唯一路径)
2. 初始化路径数为0
3. 如果 x > 0 则添加由 x - 1 产生的路径数(递归调用)
4. 如果 y > 0 则添加由 y - 1 产生的路径数(递归调用)
5. 返回添加的路径总数

请注意，您必须同时执行第 2 步和第 3 步。您的代码只执行第 2 步(成功并阻止第 3 步执行)。

编辑

如果需要自己输出路径，那么就需要在递归的时候把路径累加起来，只有到了目的地才打印出来。 (你这样做的方式——在你下降时打印每一步——是行不通的。考虑从 (2,2) 到 (0,0) 的所有路径，这些路径经过 (1,1)。每个路径段从 (2 ,2) 到(1,1) 需要打印多次:从(1,1) 到(0,0) 的每个路径段打印一次。如果你在递归时打印，你不能这样做。)

实现此目的的一种方法是将路径编码为一个长度等于预期路径长度的数组(所有路径都恰好是 x + y 步长)并在进行时填写它带有您移动方向的代码。这是一种方法:

static const int DOWN = 0;
static const int RIGHT 1;
int findPath(int x, int y, int *path, int len) {
    if (x == 0 && y == 0) {
        printPath(path, len);
        return 1;
    }
    int n = 0;
    if (x > 0) {
        path[len] = DOWN;
        n += findPath(x-1, y, path, len + 1);
    }
    if (y > 0) {
        path[len] = RIGHT;
        n += findPath(x, y-1, path, len + 1);
    }
    return n;
}

void printPath(int *path, int len) {
    if (len == 0) {
        cout << "empty path";
    } else {
        cout << (path[0] == DOWN ? " d" : " r");
        for (int i = 1; i < len; ++i) {
            cout << " -> " << (path[i] == DOWN ? " d" : " r";
        }
    }
    cout << endl;
}

你可以这样调用:

int *path = new int[x + y];
cout << "Number of paths: " << findPath(x, y, path, 0) << endl;
delete [] path;