Понимание рекурсии в Java

Question

Мне сложно понять следующий код, основанный на алгоритме рекурсии в Java. Я не понимаю, какое значение имеют x и y, когда они вызывают друг друга? Я пытался получить правильное значение, вызывая System.out.print() внутри кода, но все равно не получил помощи.

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

Я не мастер программирования, и я пытаюсь изучать Java на практике. Любая помощь приветствуется.

Answer 1

По сути, это продолжает называть себя, пока вы не достигнете третьей итерации (x==3).

Итак, вот поток (минус два вызова maxSum в max ... для простоты) (каждый отступ - это вызов 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 2

Самый простой способ понять, что происходит с рекурсивной функцией, - вынуть карандаш и бумагу и записать каждый шаг, пока не дойдете до базового случая (в этом уравнении, когда x == 3). Затем работайте в обратном направлении, вставляя возвращаемые значения в предыдущих шагах. Здесь у вас есть рекурсия головы, ситуация, когда среда выполнения должна решать каждый шаг и возвращаться с каждого шага, пока не вернется к исходному вызову, и к тому времени вы получите свой ответ.

Answer 3

Значения x и y, на которые вы ссылаетесь, ссылаются на конкретные числа в числовой пирамиде.

Что делает ваш алгоритм, так это находит максимальный путь вниз по пирамиде, добавляя верхнюю цифру, а затем разделяя большую пирамиду на две меньшие:

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

и

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

.

Затем он делает тот же процесс на меньших пирамидах (я просто сделаю это с верхней):

    {2},
    {8 ,5}

и

    {4},
    {5, 9}

.

Теперь вы можете видеть, что когда он разбивает эти пирамиды, он просто остается с 2 числами, поэтому он возвращает их. Когда он поднимается обратно в стек, он сравнивает возвращаемые значения и возвращает большее.

В конце концов мы добираемся до вершины грубой силой, проверяя каждый след в пирамиде.

(кстати, та же проблема на projecteuler.net)

Answer 4

Значения x и y просты в качестве аргументов - просто посмотрите на множество вызовов maxSum: сначала они равны 0 и 0, на каждом следующем шаге x + 1 и y + 1 (и x +1 и y) по сравнению с предыдущим шагом, останавливаясь, когда x достигает 3. Итак, составьте таблицу, а точнее дерево ...:

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

... и все!