Ejercicio 3

Ejercicio 3

de Nicolas Brignoni Dardano -
Número de respuestas: 3

Buenas estaba haciendo este ejercicio y me surgieron algunas dudas que prefiero despejar. En mi caso el código de la función es el siguiente 

uint Rayuela(uint n){
    if ((n==0)||(n==1))
      return 1;
    else
      return Rayuela(n-1) + Rayuela(n-2);

Esto es porque si partís de [0,1,2,3,4,.....,n]  cada vez que das un salto de uno y quedas en el uno [1,2,3,4,.....,n]  tenes los mismos camino posibles que ir de 0 a n-1 [0,1,2,3,4,.....,n-1]  es decir rayuela(n-1), pero si en cambio decidís en el primer movimiento saltar a la segunda baldosa eso es [2,3,4,.....,n]  es equivalente a ir de o a n-2 [0,1,2,3,4,.....,n-2]  entonces suponiendo que accionando análogamente el algoritmo recurrente ya calcula Rayuela(n-1) y Rayuela(n-2) ya estaría lista la función. 

Estuve viendo que hay varios ejercicios en los que se pide recursión de cola, esto no seria recursión de cola cierto? Hay funciones recurrentes que no se pueden llevar a recursión de cola?

Saludos.

En respuesta a Nicolas Brignoni Dardano

Re: Ejercicio 3

de Federico Andrade -
Hola Nicolás,
Me parece que tu código funciona bien. No se si me convence del todo la justificación, pero el código parece correcto.
Sobre la pregunta, esto no es recursiòn de cola ya que estás haciendo acciones posteriores a la llamada recursiva, concretamente la suma de los valores resultantes. Sobre la segunda pregunta, en general para pasar una función de recursión clásica a recursión de cola necesitas ir haciendo el cálculo antes y mantener un valor almacenado. No estoy seguro si cualquier recursión clásica se puede llevar a recursión de cola. Lo pienso un poco y te vuelvo a escribir,

Saludos,

En respuesta a Federico Andrade

Re: Ejercicio 3

de Nicolas Brignoni Dardano -
Dale muchas gracias! Sobre la forma de pensarlo, no se si es la correcta pero con un ejemplo concreto seria [0,1,2,3] entonces acá tenes la disyuntiva si avanzas uno o dos en el primer paso.

(1) Si es 1, entonces queda [1,2,3] y eso tiene tantas formas posibles de llegar de 1 a 3 como los tiene [0,1,2]
  • (1.1) y si de nuevo saltas a 1 tenes [2,3] o según el razonamiento [0,1] donde caes en un caso base (n=1) retorna 1.
  • (1.2) si en vez de saltar 1 salta 2 queda en esta situación [3] o de nuevo [0] caso base que devuelve 1
Entonces si a la primera salta 1 tiene dos formas de llegar de 0 a 3.

(2) Si en el primer movimiento salta 2 sucede lo siguiente [2,3] que requiere tantos pasos como [0,1] sale por caso pase que devuelve 1.

entonces rayuela(3) =[ (1+1) que se corresponde a saltar 1 la primera ves ] + [ (1) que corresponde a saltar 2 ]

Use este ejemplo porque es los bastante corto como para "ejecutarlo" a mano y ademas n=3 es el que daba la letra que tenia justamente tres formas de ir.

Mientras lo escribía se me ocurrió que tal vez si no termina de cerrar. Pero bueno ya lo escribí y quedo
Un saludo.
En respuesta a Nicolas Brignoni Dardano

Re: Ejercicio 3

de Federico Andrade -
Hola Nicolás,

Gracias por la aclaración, ahora se entendió mejor y me parece que el razonamiento está bien hecho, porque efecticamente lo que importa en este ejercicio para encontrar la cantidad de combinaciones son la cantidad de adoquines que separan la salida de la llegada y no la dirección en la que vas.

Sobre la pregunta que había quedado sin responder, no toda recursión general se puede llevar a recursión de cola. En la recusión de cola lo último que haces es el llamado recursivo. Si por ejemplo tenés una función que necesite hacer dos llamados recursivos no la podés llevar a recursión de cola.

Saludos