No entiendo recursividad!!!!!

[FelipeGomez]

Una duda nuestra profesora nos dejo un problema de recursividad
Hacer un programa  recursivo que resuelva el siguiente planteamiento:
Definir una matriz de nXn. Igual número de fila que de columnas
esto es una serie de compuertas en cada lugar donde hay una C hay un coyote, si una gallina quiere pasar al otro lado, que casilla debe tomar para poder pasar.
Hacer un programa que examine  las compuertas y muestre a la gallina los lugares que puede pasar para llegar al otro lado.

pero solo mostró un ejemplo de fibonacci y factorial, pero es muy sencillo y me dejo igual
Ejemplo que mostro:

Código: [Seleccionar]

private static int Fibonacci(int num){

 if(num == 0 || num==1)

    return num;

 else

    return Fibonacci(num-1) + Fibonacci(num-2);

     }



[Kabuto]

Hola.
Tal y como he entendido el ejercicio (que quizás lo he entendido mal), usar recursividad aquí no parece lo más óptimo. Pero supongo que lo importante es entender la recursividad, sin importar si este es el mejor escenario para usarla.

A ver, para usar recursividad tenemos que usar una función. Y una función ha de retornar un valor.

Así que hay que pensar en que valor necesitamos retornar.
Tenemos una matriz y hay que indicar que compuerta es la segura. De hecho, puede haber más de una.
Las compuertas son posiciones de la matriz, así que se identifican con dos valores, es decir, dos índices: [0,3], [4,2], etc...

Bien, suponiendo que solo hubiera una compuerta sin coyote, ya tendríamos un problema porque la función solo puede retornar UN valor pero para identificar una compuerta hemos dicho que necesitamos DOS índices.
Lo podríamos solucionar retornando un arreglo de dos elementos, uno para cada índice.

Pero es que en realidad, puede haber más de una compuerta sin coyote, así que no sabemos si vamos a retornar DOS índices, o CUATRO, u OCHO, ...o CIEN MIL......
Así que no nos sirve la idea de retornar un arreglo.

Pero, siendo un poco listos, lo que podemos hacer es retornar un String. En ese String, se pueden ir concatenando las parejas de índices que identifiquen compuertas seguras.
De este modo en UN único valor (un String), podemos tener todos los índices que queramos.

Bien, ya hemos decidido que tipo de dato va a retornar la función recursiva. Ahora hay que decidir cuáles son los argumentos que (lo que va entre paréntesis) hay que aportar en cada llamada a la función.
Es decir, la función se va a ir llamando a sí misma un número indeterminado de veces y en cada llamada hay que aportarle unos argumentos para evaluar.

Un argumento está claro que será la matriz de "compuertas".

Para recorrer la matriz, va a necesitar dos índices, así que también le pasaremos dos valores int. Estos valores int, incrementarán su valor en cada llamada recursiva para que en cada iteración se compruebe una posición de la matriz distinta. Será parecido a cuando usamos dos bucles anidados para recorrer una matriz.

Otro argumento que hay que proporcionar, será el String donde se anoten las posiciones válidas. Este String ha de ir "viajando" en cada llamada recursiva para que se actualice su información en caso de encontrar una compuerta segura.

Ok, pues esta sería la "firma" de nuestra función, que yo la he llamado examinar():

Código: [Seleccionar]

private static String examinar(char[][] matriz, int i, int j, String seguras)Como hemos dicho, sus argumentos son la matriz, dos indices para recorrer la matriz y un String para apuntar las compuertas seguras.
Precisamente este String, será el que esta función retornará cuando finalice su proceso recursivo.

Vamos a pensar ahora en su código.
El código de una función recursiva, siempre tiene como mínimo dos sentencias RETURN.
Un return será una llamada recursiva a sí misma, prolongando su proceso.
El otro return, será el del valor final ya procesado, lo cuál pone fin a todo el proceso recursivo.

Hacer un return u otro, obviamente dependerá de si se cumplen unas condiciones u otras.

Yo por lo general, el código lo comienzo escribiendo las condiciones que van a poner fin al proceso recursivo.
¿Y cuáles son esas condiciones? ¿Cuándo queremos que el proceso termine?
Pues si el objetivo es recorrer la matriz de principio a fin, el proceso ha de terminar cuando ambos índices hayan alcanzado los límites de la matriz (longitud de la matriz - 1).
Para entonces ya no quedarán "compuertas" para comprobar y podremos retornar el String con la lista de compuertas seguras:

Código: [Seleccionar]

private static String examinar(char[][] matriz, int i, int j, String seguras) {
if (i == matriz.length - 1 && j == matriz.length - 1)//Ambos índices están en el límite
return seguras; //Ya se ha recorrido toda la matriz
else  {........
Sigamos, ¿y si aún quedan compuertas por comprobar?
Vale, pues entonces comprobamos si la compuerta actual, la que nos van a indicar los indices i y j, hay un coyote o no.

Si no hay coyote, entonces esta "compuerta" es segura y concatenamos su dirección en el String donde anotamos los índices de compuertas sin coyotes.
Si hay coyote, entonces no haremos nada, así que ni siquiera lo vamos a preguntar.

Con o sin coyote, una vez comprobada la compuerta hay que pasar a la siguiente, es decir, hay que incrementar los índices.
Lo haremos de forma análoga a como se haría si estuvieramos usando dos bucles anidados.
Comprobamos si el indice j se puede incrementar. Si está por debajo del límite de la matriz, se incrementa y listo.
Si está en el límite, entonces retoma valor 0 y es el índice i el que se incrementa

Tras esto, ya tenemos los índices actualizados y listos para pasar a la siguiente compuerta, es decir, hacemos una nueva llamada recursiva a la función, aportando todos los argumentos que han de acompañar esa llamada.

Código: [Seleccionar]

private static String examinar(char[][] matriz, int i, int j, String seguras) {
if (i == matriz.length - 1 && j == matriz.length - 1)//Ambos índices están en el límite
return seguras; //Ya se ha recorrido toda la matriz
else  {
//Comprobamos la compuerta actual
if (matriz[i][j] != 'C')  //Aquí NO hay coyote
seguras += String.format("[%s,%s]\n", i,j);//Añadimos esta posición a la lista de "seguras"

//Ahora incrementamos los índices, vigilando los límites de la matriz
if (j < matriz.length - 1)//Segundo índice está por debajo del límite
j++; //Se puede incrementar
else { //Segundo índice está en el límite
j = 0; //Vuelve a 0...
i++; //...y se incrementa el primer índice
}
//Índices actualizados, hacemos llamada recursiva
return examinar(matriz, i, j, seguras);
}
}

Pues ya tenemos la función recursiva. Ahora hay que ponerla a prueba.
Hacemos un método main, construimos una matriz y llamamos a nuestra función para que construya y retorne un String con las posiciones seguras.

Fíjate que al llamar la función en el programa, tenemos pasarle dos valores 0 para los índices (para que empiece desde el principio de la matriz) y una cadena String vacía que será donde se concatenen las posiciones de compuertas seguras:

Código: [Seleccionar]

public static void main(String[] args) {

char[][] compuertas = {
{'C', 'L', 'L', 'C', 'C'},
{'L', 'L', 'C', 'C', 'C'},
{'C', 'C', 'C', 'C', 'C'},
{'C', 'C', 'L', 'C', 'C'},
{'C', 'C', 'C', 'C', 'C'},
};

System.out.println("Lista de compuertas seguras:");
System.out.println(examinar(compuertas, 0, 0, ""));

}
Si lo ejecutamos, en pantalla veremos la lista de posiciones sin coyotes:

Lista de compuertas seguras:
[0,1]
[0,2]
[1,0]
[1,1]
[3,2]

Y eso es todo.
Repito que no se si he entendido bien el ejercicio, pero de todos modos, hemos creado un ejemplo de recursividad.
Espero que se haya entendido, pregunta lo que sea necesario.

Un saludo.

[FelipeGomez]

Muchísimas gracias.
Entonces para la recursividad podemos diseñar una estructura de if en donde definimos las acciones y los indices, ya con los indices definimos la poción según las coordenadas y en string el resultado, luego consultamos si es seguro y el fin de los ejercicios es alcanzar el limite.
Entonces también podemos ocupar return para "actualizar" la variable en una forma recursiva, eso no lo sabia
Ok ya le entendí, de verdad muchísimas gracias

[Kabuto]

En este caso usamos índices, porque los necesitamos para esta tarea.
No significa que para recursividad se necesiten índices siempre.

La recursividad básicamente consiste en hacer que una función se llame a sí misma una y otra vez hasta que se cumpla una determinada tarea, momento en el que se retorna el resultado computado.

En cada llamada recursiva, hay que pasar uno o más valores. Estos valores no pueden ser siempre los mismos (porque entonces la recursividad se vuelve infinita), en cada llamada han de ser modificados de alguna manera.
Qué valores hay que pasar, qué operaciones hay que realizar, que resultado hay que computar... pues todo depende de la tarea que se solicite.

La recursividad no es una solución a un problema, es una forma de procesar la solución. Pero la solución en sí tiene que decidirla el programador.

Un saludo.