Entendiendo la doble recursividad

Por fin luego de tanto luchar pudimos encontrar el arreglo de este conflicto que agunos lectores de nuestro espacio presentan. Si quieres aportar algún detalle no dudes en dejar tu comentario.

Solución:

Parece que ya comprende el caso base y sabe cómo funciona la recursividad, por lo que el key entender su ejemplo particular es notar que dada la inicial array

a = [1,2,10,15,16,4,8]

estás, en el “nivel superior” calculando dos cosas:

maxval1 = MaximumElement(array, 0, 3); 
maxval2 = MaximumElement(array, 3, 4);

que dice

• hacer maxval1 el valor máximo de la array en el rango a partir del índice 0 de tamaño 3
• hacer maxval2 el valor máximo de la array en el rango de índice 3 de tamaño 4

Asi que

• maxval1 de hecho serán 10
• maxval2 de hecho serán 16

y tu respuesta será 16.

Lo bueno de la recursividad es que no tienes que preocuparte por rastrear demasiado las cosas. Si confía en su caso base y en la manera en que llega a su caso base, entonces comprender un nivel debería ser suficiente.

Creo que te quedaste atascado donde dijiste “se desata el infierno” porque la segunda llamada recursiva comienza con un índice inicial de 0. No es así. Comienza en el índice 3. (Es decir, asumiendo que su segunda llamada recursiva es la que calcula maxVal2).

Aquí hay un rastro abreviado de cómo funciona su cálculo. Me he tomado la libertad de cambiar el nombre de su función a m y suponer que maxVal1 y maxVal2 se calcularon un poco más “funcionalmente”.

a = [1,2,10,15,16,4,8]

m(a, 0, 7)
= m(m(a, 0, 3), m(a, 3, 4))
= m(m(m(a, 0, 1), m(a, 1, 2)), m(a, 3, 4))
= m(m(a[0], m(a, 1, 2)), m(a, 3, 4))
= m(m(1, m(a, 1, 2)), m(a, 3, 4))
= m(m(1, m(m(a, 1, 1), m(a, 2, 1)), m(a, 3, 4))
= m(m(1, m(a[1], a[2])), m(a, 3, 4))
= m(m(1, m(2, 10)), m(a, 3, 4))
= m(m(1, 10), m(a, 3, 4))
= m(10, m(a, 3, 4))
= …
= 16

No estoy seguro de poder explicarlo muy bien, pero lo explicaré usando fibonacci en su lugar. Una forma recursiva para calcular los números de Fibonacci son:

public static int getFib(int n) 
    if(n <= 2) return 1;
    return getFib(n-1)+getFib(n-2);

Lo que realmente sucede en el código es que, obviamente, bajará las llamadas al método hasta que obtenga un primer retorno. Asi que getFib(n-1) Seguirá siendo llamado hasta n <= 2 luego volverá a la pila de métodos y, dado que ahora tiene un valor para getFib (n-1), llamará a getFib (n-2). Entonces, digamos que nuestra llamada inicial es con 4, lo que sucede es:

getFib(4) //Initial call
  getFib(4-1=3) //Left hand recursive call level 1
    getFib(3-1=2) //Left hand recursive call level 2
      return 1 //This would be level 3
    getFib(3-2=1) //Right hand recursive call level 2
      return 1 //level 3
  getFib(4-2=2) //Right hand recursive call level 1
    return 1

No estoy seguro de si eso tiene algún sentido, esta imagen podría visualizarlo un poco:

_{(fuente: fortystones.com)}

El código anterior básicamente haría un recorrido en profundidad primero (tomando primero a los niños de la izquierda) a través de ese árbol.

Me parece que ha confundido el orden de ejecución de las llamadas recursivas. Tenga en cuenta que la segunda llamada (maxval2) no se llama hasta que finaliza la primera llamada (maxval1). La llamada maxval1 en sí misma tiene dos llamadas recursivas más dentro de sí misma y así sucesivamente. Entonces, sin que se terminen todas estas llamadas recursivas internas, el programa no llega a la línea maxval2.

Intente depurar en lugar de ejecutar el código (en Eclipse, por ejemplo) y avance paso a paso para ver cómo funciona cada llamada recursiva.

Sección de Reseñas y Valoraciones

Si estás de acuerdo, puedes dejar una reseña acerca de qué te ha parecido esta noticia.

---

---

Utiliza Nuestro Buscador