Problem in Algorithm Recursive?

Hello friends, I have a problem to implement a recursive version of an algorithm that I made, I get different values, I hope you can help me, here are the code so Iterative (OK) and Recursive code form that is not OK.

The data sets do not give equal:

The algorithm is given two source and target positions on a board, find the number of paths between them...

Input Example: 5
2 3
4 4
Output Example:

5



I hope its not help that I'm wrong!!!

Iterative Algorithm ( OK )

Code:

---

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>

using namespace std;
int n , dp [1000][1000], x, y, xx, yy;
bool mark [1000][1000];

struct Punto
{
    int x;
    int y;
};

Punto inicio, fin , aux;
queue < Punto > lista;
int direcciones[3][2] = { {0,1}, {1,0}, {1,1} };

void BFS()
{
    lista.push(inicio);
    dp[ inicio.x ][ inicio.y ] = 1;
    while( !lista.empty() )
    {
        aux = lista.front();
        lista.pop();
        x = aux.x;
        y = aux.y;
        for(int i=0 ; i<3 ; i++)
        {
            xx = direcciones[i][0]+x;
            yy = direcciones[i][1]+y;
            if( xx>0 && xx <= n && yy > 0 && yy <= n )
            {
                dp[xx][yy] += dp[x][y];
                if(!mark[xx][yy])
                {
                    mark[xx][yy] = true;
                    aux.x = xx;
                    aux.y = yy;
                    lista.push( aux );
                }
            }
        }
    }
}

int main()
{   
    cin>>n;
    cin>>x>>y;
    inicio.x = x;
    inicio.y = y;
    cin>>x>>y;
    fin.x = x;
    fin.y = y;
    BFS();
    cout<< dp[fin.x][fin.y] <<endl;
    system("pause");
    return 0;
}

---

Recursive Algorithm ( not OK )

Code:

---

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int n , dp [1000][1000], x, y, xx, yy;
bool mark [1000][1000];

struct Punto
{
    int x;
    int y;
};

Punto inicio, fin , aux;
queue < Punto > lista;
int direcciones[3][2] = { {0,1}, {1,0}, {1,1} };

void BFS(Punto aux){
        x=aux.x;
        y=aux.y;
        for(int i=0;i<3;i++){
                xx=direcciones[i][0]+x;
                yy=direcciones[i][1]+y;
                if( xx>0 && xx <= n && yy > 0 && yy <= n )
                {
                        dp[xx][yy] += dp[x][y];
                        if(!mark[xx][yy])
                        {
                                mark[xx][yy] = true;
                                aux.x = xx;
                                aux.y = yy;
                                BFS( aux );
                        }
                }
        }
}

int main()
{
    cin>>n;
    cin>>x>>y;
    inicio.x = x;
    inicio.y = y;
    cin>>x>>y;
    fin.x = x;
    fin.y = y;
 
    dp[ inicio.x ][ inicio.y ] = 1;
    BFS(inicio);
 
    cout<< dp[fin.x][fin.y] <<endl;
    system("pause");
    return 0;
}

---

I hope its not help that I'm wrong!!!
cronos

Quote:

---

Originally Posted by carburo

Hello friends, I have a problem to implement a recursive version of an algorithm that I made, I get different values, I hope you can help me, here are the code so Iterative (OK) and Recursive code form that is not OK.

---

So what debugging have you done? Where does the recursive function make the wrong decision? What have you discovered by debugging?

Or are you waiting for a professional or expert programmer to debug your program? (which would be considered cheating if this is some sort of school or homework assignment)

Regards,

Paul McKenzie

Before writing the code, you have produced program designs for both the iterative and recursive versions - and walked through them on paper to make sure the designs were correct haven't you? So either you have not coded correctly the working design or your design is wrong. When confronted with a problem such as this, it is very important that a proper program design is produced before coding. You just can't start coding without having a proven program design first. Debugging as suggested by Paul in post #2 will either suggest that your design is correct but your coding is wrong - or your design itself is wrong. If its just coding of the design implementation that's wrong, it should be fairly easy to spot with the debugger. However, if debugging indicates that it's the design itself that's wrong, then IMO I would revisit the design and correct that first rather than trying to fix the design problem as part of the code debugging. Once the design is corrected, then re-code from the modified design.