Zrozumieć rekursję w Javie

Question

Mam trudny czas na zrozumienie następującego kodu na podstawie algorytmu rekursji w Javie. Nie rozumiem, jaka jest różna wartość x i y, gdy dzwonią do siebie nawzajem? Próbowałem uzyskać odpowiednią wartość, dzwoniąc pod numer System.out.print(), ale nadal nie otrzymałem pomocy.

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

Nie jestem mistrzem programowania, a ja próbuję uczyć się Javy. Każda pomoc jest doceniana.

Answer 1

Wartości xiy, do których odnosi się link do określonych liczb w piramidzie liczb.

Co robi Twój algorytm jest znaleźć maksymalną drogę w dół piramidy dodając na najwyższym cyfry, a następnie dzieląc dużą piramidę na dwa mniejsze:

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

i

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

.

Następnie wykonuje te same czynności na mniejszych piramid (ja po prostu zrób to z górnej jeden):

{2}, 
    {8 ,5} 

i

{4}, 
    {5, 9} 

.

Teraz możesz zobaczyć, że kiedy łamie te piramidy, pozostaje tylko 2 cyfry, więc je zwraca. Gdy wspina się na stos, porównuje zwrócone wartości i zwraca większy.

Ostatecznie trafiamy na szczyt brutalną siłą sprawdzając każdy szlak w piramidzie.

(Nawiasem mówiąc, ten sam problem jest na projecteuler.net)

Answer 2

Wartości X i Y są proste, jak oni argumenty - wystarczy spojrzeć na wiele połączeń do maxSum: najpierw oni 0 i 0, przy każdym następnym kroku x + 1 i y + 1 (oraz x + 1 i y) w poprzednim kroku, zatrzymując się, gdy x otrzyma wartość 3. Zrób stolik, a raczej drzewo ...:

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 

... i to wszystko!

Answer 3

Zasadniczo to wywołuje się, dopóki nie dojdziesz do trzeciej iteracji (x==3).

Więc oto przepływu (minus dwa połączenia do maxSum w max ... dla uproszczenia) (każdy akapit jest wezwaniem do 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

Najprostszym sposobem, aby zrozumieć, co się dzieje funkcją rekurencyjną jest wyciągnięcie ołówka i papieru i zapisywanie każdego kroku, aż dojdziesz do przypadku podstawowego (w tym równaniu, gdy x == 3). Następnie stamtąd zacznij od tyłu, podłączając zwracane wartości w poprzednich krokach. To, co tu masz, to rekursja głowy, sytuacja, w której środowisko wykonawcze musi rozwiązać każdy krok i powrócić z każdego kroku, aż do powrotu do pierwotnego połączenia, do którego czasu otrzymasz odpowiedź.