where i am wrong in this recursion

Question

Sir, these days i am improving my recursion skills but i am stuck in one of the recursion problem of "Cracking the coding skills" book. Problem number 8.2
Problem statement is -- Imagine a robot sitting on the upper hand corner of an N*N grid. The robot can only move in two directions: right and down. How many possible patha are there for the robot ?

I tried a lot but it only shows me a single path. My code is (taking help from solution of book)

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

I put printf statement to check where i am wrong, but i didn't find mistake. Please help me.

I wrote the code given by your instructions. But , if I want to print all the paths, it gives undesired answer.

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

for grid of 3*3 It gives ( findPaths(2, 2) ) :-

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

Answer 1

Your problem is that, when x >= 1, you are decrementing x and setting success to true. That prevents your code from exploring decrementing y.

The proper recursion rules are:

1. If x == 0 && y == 0, return 1 (the empty path is the only path)
2. initialize the number of paths to 0
3. if x > 0 then add the number of paths that result from x - 1 (recursive call)
4. if y > 0 then add the number of paths that result from y - 1 (recursive call)
5. return the total number of paths added

Note that you must execute both steps 2 and 3. Your code is only executing 2 (which succeeds and prevents step 3 from executing).

EDIT

If you need to output the paths themselves, then you need to accumulate the path as you recurse and print it out only when you get to the destination. (The way you are doing it—printing each step as you descend—won't work. Consider all paths from (2,2) to (0,0) that go through (1,1). Each path segment from (2,2) to (1,1) needs to be printed multiple times: once for each path segment from (1,1) to (0,0). If you print as you recurse, you can't do this.)

One way to do this is to encode the path in an array of length equal to the expected path length (all paths will be exactly x + y steps long) and fill it in as you go with a code for which direction you moved. Here's one way:

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

You could call this with:

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