CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Problem in Algorithm Recursive?

1. Junior Member
Join Date
May 2013
Posts
2

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

2. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

## Re: Problem in Algorithm Recursive?

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.
Don't post on multiple forums. I asked you on the other forum as to what debugging have you done.

Regards,

Paul McKenzie

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•