Понимание рекурсии с сортировкой слиянием

Я вижу некоторые сообщения, чтобы понять сортировку слиянием. Я знаю, что рекурсивные методы поддерживают стек для хранения значений. (насколько я понимаю, результат оператора return будет в стеке)

private int recur(int count) {
    if (count > 0) {
        System.out.println(count);
        return count + recur(--count); // this value will be in stack.
    }
    return count;
}

Я запутался в сортировке слияния, как здесь поддерживается стек.

private void divide(int low, int high) { 
    System.out.println("Divide => Low: "+ low +" High: "+ high);
    if (low < high) {
        int middle = (low + high) / 2; 
        divide(low, middle); // {0,7},{0,3}, {0,1} ;
        divide(middle + 1, high); // {0,0};  high = 1; // 2nd divide
        combine(low, middle, high);
    }
}
  1. Есть стек для всех локальных переменных?
  2. При вызове 2-го рекурсивного метода также присоединится 1-й рекурсивный? Как поддерживается стек в таких случаях?

recursion mergesort
person CHowdappaM    schedule 27.02.2017    source источник
comment
Это лучше всего объясняет.   -  person sweta.me    schedule 27.02.2017
comment
Вы поймете рекурсию намного легче с более простыми задачами. Еще до этого вы должны изучить, что такое стек, как вызываются функции и какие значения помещаются в стек, как возвращаемые значения передаются вызывающей стороне и как параметры передаются функции.   -  person Selçuk Cihan    schedule 27.02.2017

Ответы (1)


arrow_upward
0
arrow_downward

Вам нужно только знать, что оператор должен завершиться и вернуться, и что вы вызываете divide или combine из divide, работает так же. Оба должны быть завершены до того, как можно будет выполнить следующую строку кода, или, если строк больше нет, функция вернется. Да, это делается со стеком, но на самом деле это не важно.

  1. Состояние переменных ожидания low, high и middle - это только текущие привязки вызовов, поэтому они не смешиваются с другими вызовами.

  2. Каждый раз, когда вы вставляете новый вызов, он получает свои собственные переменные, и каждую из них нужно завершить. Когда нижний-средний завершается, он вызывает средний + 1-высокий, а когда он завершается, объединяется. Эти вызовы будут делать то же самое, поэтому у вас будет более глубокая вложенность, и то, как будет посещаться структура вызовов, будет похоже на структуру двоичного дерева с листьями, являющимися low == high (один элемент).

Небольшой совет. При просмотре рекурсивного кода попробуйте перейти от листа к более сложному дереву. например. сначала попробуйте использовать базовый вариант, а затем простейший вариант по умолчанию. например.

  1. Массив из 1 элемента: ничего не делает
  2. 2-элементный массив: -> 1-элементный массив (см. 1.), 1-элементный массив, объединить
  3. 4-элементный массив: -> 2-элементный массив (см. 2.), 2-элементный массив, объединить

Обратите внимание на то, что 2. вы знаете, что оба рекурсивных вызова ничего не сделают, а combine, возможно, произведет обмен. 3. выполняет 2. дважды (включая своп) перед combine, который объединит 2 массива из 2 элементов, которые будут отсортированы. Возможно, вы смотрите на это с другой стороны, что требует, чтобы вы остановили 3. чтобы сделать 2., что остановит его и сделает 1., затем следующую 1, затем обратно к 2., чтобы сделать текст с двумя единицами ... Для этого нужны ручка и бумага. Глядя на него от листа к корню, используя то, что вы узнали о нем, вы сможете понять его намного проще. Я действительно считаю, что функциональную рекурсию легче понять, чем изменять структуры, подобные вашей сортировке слиянием. например. последовательность Фибоначчи.

person Sylwester    schedule 27.02.2017