Понимание рекурсии в Java
Выделение стека Usually просто состоит из вычитания из регистра указателя вершины стека. Это - тонны быстрее, чем поиск "кучи".
выделение стека Sometimes требует добавления страницы (страниц) виртуальной памяти. Добавление новой страницы обнуленной памяти не требует читать страницу от диска, таким образом, обычно это все еще будет тоннами быстрее, чем поиск "кучи" (особенно, если часть "кучи" была разбита на страницы также). В редкой ситуации, и Вы могли создать такой пример, достаточно пространства просто, оказывается, доступно в части "кучи", которая уже находится в RAM, но выделение новой страницы для стека должно ожидать некоторой другой страницы, которая будет выписана к диску. В той редкой ситуации "куча" быстрее.
4 ответа
По сути, он продолжает вызывать себя, пока вы не дойдете до третьей итерации ( 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
Значения x и y, которые вы имеете в виду, связаны с конкретными числами в числовой пирамиде.
Ваш алгоритм находит максимальный путь вниз по пирамиде, добавляя к верхней цифре, затем разделение большой пирамиды на две меньшие:
{7},
{2, 4},
{8 ,5, 9}
и
{4},
{4, 6},
{5, 9, 3}
.
Затем тот же процесс выполняется с меньшими пирамидами (я просто сделаю это с верхней):
{2},
{8 ,5}
и
{4},
{5, 9}
.
Теперь вы можете видеть, что когда он разбивает эти пирамиды, у него остается только 2 числа, поэтому он их возвращает. По мере того, как он поднимается вверх по стеку, он сравнивает возвращенные значения и возвращает большее.
В конце концов, мы добираемся до вершины путем грубой силы, проверяя каждый след в пирамиде.
(Кстати, та же проблема есть на projecteuler.net)
Самый простой способ понять, что происходит с рекурсивной функцией, - это достать карандаш и бумагу и записывать каждый шаг, пока вы не дойдете до базового случая (в этом уравнении, когда x == 3). Затем работайте в обратном направлении, вставляя значения, возвращенные на предыдущих шагах. У вас есть рекурсия головы, ситуация, когда среда выполнения должна решать каждый шаг и возвращаться с каждого шага, пока не вернется к исходному вызову, и к этому времени вы получите ответ.
Значения 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
... и все!