Problema en algoritmo recursivo!!!

[mariamgn]

Hola amigos, tengo un problema al implementar una version recursiva de un algoritmo que he realizado, me da valores distintos, espero que puedan ayudarme, aca les dejo el codigo de forma Iterativa ( OK ) y el codigo de forma Recursiva que no esta OK.

Los juegos de datos no dan iguales:

El algoritmo trata de dada 2 posiciones de origen y destino en un tablero, buscar la cantidad de caminos entre ellos.


espero su ayuda no se en que me equivoco

Algoritmo Iterativo (OK)

Código:

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

Algoritmo Recursivo mal

Código:

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

saludos
cronos

[razpeitia]

Código C++:

#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()
{
    
    if( !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 );
                }
            }
        }
        BFS();
    }
}
 
int main()
{    
    cin>>n;
    cin>>x>>y;
    inicio.x = x;
    inicio.y = y;
    cin>>x>>y;
    fin.x = x;
    fin.y = y;
 
    lista.push(inicio);
    dp[ inicio.x ][ inicio.y ] = 1;
    BFS(); 
    cout<< dp[fin.x][fin.y] <<endl;
    return 0;
}
 

[mariamgn]

Hola razpeitia, usted me ha puesto 1 codigo el cual no le veo nada, si pudiese explicarse que quiso decir con ello?

saludos
cronos

[razpeitia]

Es el algoritmo recursivo que pidió.

Simplemente en lugar del while lo cambie a una recursion y el código que tenia al principio lo puse antes de ejecutar esa función.

Es el mismo código que tu programa iterativo solamente cambie 4 lineas. 2 las movi de lugar, una la añadi y otra le cambie unos cuantos caracteres.

En mi opinión pensar de manera recursiva no es tan difícil, solamente piensas como si las funciones fueran sándwiches.

[mariamgn]

Hola, gracias por su respuesta, ahhora una pregunta que tipo de resursividad es la que se usa en este algoritmo, y he oido que existe el tipo complejidad u orden para los algoritmos recursivos, en este caso como hallo esto?

saludos
mariam

[razpeitia]

Tiene la misma complejidad que algoritmo iterativo ya que usa recursion simple.

Puedes usar el Master theorem para obtener la complejidad de un algoritmo recursivo.

En este caso pasar BFS de iterativo a recursivo es el peor ejemplo que tu maestro te pudo haber puesto. Por que realmente no hay recursion significativa.

Un ejercicio como pasar de:

Código C++:

for(int i = 0; i < 10; i++)
    printf("%d\n", i);
 

A una función recursiva tiene el mismo valor que tu ejercicio.

Algunos ejercicios que te pueden servir:
1. Factoriales (recursiva e iterativa)
2. Números de fibonacci (recursiva e iterativa)
3. Dado un numero imprime (por ejemplo 5) imprime: 123454321 (recursiva e iterativa)