Рекурсия - пытаясь понять

Question

У меня есть следующий метод:

public static int maxFind(int [] a, int length) 
{ 
    if (length == 1){ 
      return a[0]; 
    } 

    // recursively maxFind method on length-1 
    int result = maxFind(a, length - 1); 

    if (a[length - 1] > result) 
    return a[length - 1]; 
    else 
    return result; 

} 

Я закончил эту работу, и пройти некоторое время с момента, когда я увидел учебник этого метода и я всегда забываю идею рекурсии. Я думаю, что если кто-то объяснит мне каждый шаг этого метода - я получу идею раз и навсегда.

Примера - моя аранжировка является: {1,1,0,2)

Что шаги здесь, когда мы работаем этот метод? какова ценность результата, и какова роль (a, length-1)? (я пробовал отладчик, но мне это не помогло)

Answer 1

Я попытаюсь объяснить шаг за шагом:

На первом вызове метода с параметрами {1,1,0,2} и 4

1) max_find ([1,1,0,2], 4) => длина не 1, так max_find будет называться снова с длиной = 4-1

2) max_find ([1,1 , 0,2], 3) => длина не равна 1, поэтому max_find будет вызываться снова с длиной = 3-1

3) max_find ([1,1,0,2], 2) => длина не 1, так max_find будет называться снова с длиной = 2-1

4) max_find ([1,1 , 0,2], 1) => длина равна 1, поэтому будет возвращено значение [0], которое равно 1

5) теперь шаг шага кода 3 оценивает результат с шага 4 => a [2-1 ] не> 1, поэтому он возвращает 1

6) теперь шаг код формы 2 оценивает результат с шага 3 => а [3-1] не> 1, так что она возвращает 1

7) теперь шаг 1 формы кода оценивает результат fr шаг 2 Ом => а [4-1]> 1, поэтому он возвращает [4-1], который является 2

сделано

Answer 2

Идея в основном состоит в том, что вы делаете точно такие же вещи снова с небольшим изменением входных данных.

Сам код прост:

• Первые if проверки на конец рекурсии
• int result линия делает рекурсию
• в конце концов вы lookes для самого большого элемента и возвращает его.

Answer 3

Позвольте мне посмотреть, могу ли я пролить свет на эту тему.

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

Давайте проверим ваш пример, вам нужно найти максимальное значение в массиве, поэтому мы разложим эту проблему в меньших задачах.

Если размер массива равен 1, есть только один элемент ... так что один из них является максимальным. Легко.

Проблема нахождения max может быть описана как: большее значение между одним элементом списка и максимальным количеством всех остальных элементов.

Это то, что вы делаете в остальной части кода. Вы применяете алгоритм к массиву от позиции 0 до длины-1, а затем сравниваете возвращаемое значение.

Эти вызовы будут создавать рекурсии дерева, значение, будет несколько вызовов «вложенными», пока каждый вызов не будет сделано с длиной = 1 (базовый случай), и затем, алгоритм начнет реконструкцию ответ ,

Лучший способ понять рекурсивный алгоритм - захватить кусок бумаги и эмулировать программу, записать значения вашего массива и значение «длина» на бумаге для каждого вызова, а затем выяснить, что происходит после того, как каждый вызов наконец достигнет базового варианта.

Для {1,1,0,2}, вы в основном получаете цепочку вызовов, что-то вроде:

max(maxFind({1,1,0}), 2) 

Где maxFind ({1,1,0}) сводится к:

max(maxFind({1,1}), 0) 

и maxFind ({1,1}) является

max(1,1) = 1 

Тогда это начинает кипеть до (это обратный порядок сверху):

max(1, 0) = 0 
max(1, 2) = 2 

Таким образом, результат будет 2.

Answer 4

то, что это значение на результат

Ну, это точка рекурсии: нет один значение результат, что может вас смутить. Значение результата в порядке, 1, 1, 1 затем 2.

Каковы шаги при использовании этого метода?

Вот что происходит:

What is the max of: {1} ? Result is: 1 
What is the max of: {(1), 1} ? Result is: 1 
What is the max of: {(1, 1), 0} ? Result is: 1 
What is the max of: {(1, 1, 0), 2} ? Result is: 2 

Обратите внимание, что отладка на самом деле не так тривиальна при работе с рекурсивными методами.Это иногда помогает гораздо больше, чтобы напечатать метод вызовов «с отступом» до уровня рекурсии, как и в этом вопросе я ответил здесь:

How do I solve the 'classic' knapsack algorithm recursively?

(конечно, вы должны как-то следить за «глубины 'рекурсивных вызовов)

и какова роль (a, length-1)? (Я пробовал отладчик, но это не помогло мне)

отладчик не может помочь вам, потому что метод использует «трюк», чтобы сохранить память в Java: в основном вход укорачивается что вам не следует разбирать весь массив. Но вы все еще рекурсивно передаете весь массив методу. Это «функциональный способ бедных людей получить список с одним меньшим элементом»;)

Вот ссылка, показывающая, как найти максимальное значение в списке на другом языке. Некоторые из них, как OCaml один, выражены в функциональной форме:

http://rosettacode.org/wiki/Greatest_element_of_a_list

Три линии OCaml (источник: Википедия):

let my_max = function 
    [] -> invalid_arg "empty list" 
    | x::xs -> List.fold_left max x xs