Comprender la recursividad en Java

Question

Me está costando trabajo entender el siguiente código basado en el algoritmo de recursión en Java. No entiendo, ¿cuál es el valor diferente que tienen x y y cuando llaman entre sí? Traté de obtener el valor correcto llamando al System.out.print() dentro de un código, pero todavía no recibo ayuda.

public class RecursionExample 
{ 

    private static int[][] arr={ 
     {3}, 
     {7, 4}, 
     {2, 4, 6}, 
     {8 ,5, 9, 3} 
    }; 

    public static int maxSum(int[][] graph, int x, int y, int sum) { 
     if (x == 3) 
     { 
      return sum+graph[x][y]; 
     } 
     int max= Math.max(maxSum(graph, x+1, y, sum), maxSum(graph, x+1, y+1, sum)); 

     sum += graph[x][y]; 
     return sum+max; 
    } 

    public static void main(String[] ar) 
    { 
     System.out.println(maxSum(arr,0,0,0)); 
    } 
} 

No soy un maestro en programación, y estoy tratando de aprender Java haciendo. Cualquier ayuda es apreciada.

Answer 1

Los valores de xey que se refieren al enlace a números específicos en la pirámide de números.

¿Qué hace su algoritmo es encontrar el máximo camino abajo en la pirámide mediante la adición de dígitos en la parte superior, luego la división de la gran pirámide en dos más pequeños:

{7}, 
    {2, 4}, 
    {8 ,5, 9} 

y

{4}, 
    {4, 6}, 
    {5, 9, 3} 

.

A continuación, lleva el mismo proceso en las pirámides más pequeñas (justo lo haré con la parte superior uno):

{2}, 
    {8 ,5} 

y

{4}, 
    {5, 9} 

.

Ahora puede ver que cuando rompe estas pirámides, solo queda con 2 números, por lo que los devuelve. A medida que sube la pila, compara los valores devueltos y devuelve el más grande.

Eventualmente, llegamos a la cima mediante la fuerza bruta comprobando cada rastro en la pirámide.

(Por cierto, el mismo problema está en projecteuler.net)

Answer 2

Los valores de x e y son fáciles ya que son argumentos - basta con ver las muchas llamadas a maxSum: en un primer momento son 0 y 0, en cada paso siguiente x + 1 e y + 1 (yx + 1 ey) wrt el paso anterior, deteniéndose cuando x llega a 3. Entonces crea una tabla, o más bien un árbol ...:

0, 0 
    1, 1 
    2, 2 
     3, 3 
     3, 2 
    2, 1 
     3, 2 
     3, 1 
    1, 0 
    2, 1 
     3, 2 
     3, 1 
    2, 0 
     3, 1 
     3, 0 

... ¡y eso es todo!

Answer 3

Esencialmente, esto sigue llamándose hasta llegar a la tercera iteración (x==3).

Por lo tanto, aquí está el flujo (menos las dos llamadas a maxSum dentro max ... por el bien de la simplicidad) (cada guión es una llamada a maxSum):

x = 0 
y = 0 
sum = 0 

x != 3 

    x = 1 
    y = 0 
    sum = 0 

    x != 3 

     x = 2 
     y = 0 
     sum = 0 

     x != 3 

      x = 3 
      y = 0 
      sum = 0 

      x == 3 
      return 0 + 8 //graph[3][0] == 8 

     max = 8 //previous return 
     sum = 0 + 2 //graph[2][0] == 2 
     return 10 //max + sum == 8 + 2 == 10 

    max = 10 
    sum = 0 + 7 //graph[1][0] == 7 
    return 17 

max = 17 
sum = 0 + 3 //graph[0][0] == 3 
return 20 

Answer 4

La forma más fácil de entender lo que está pasando una función recursiva es sacar un lápiz y papel y escribir cada paso hasta llegar al caso base (en esta ecuación, cuando x == 3). Luego trabaje hacia atrás desde allí, insertando los valores devueltos en los pasos anteriores. Lo que tienes aquí es la recursividad principal, una situación en la que el tiempo de ejecución debe resolver cada paso y regresar de cada paso hasta que regrese a la llamada original en ese momento, ya tienes tu respuesta.