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

Я могу легко понять рекурсию, если внутри функции есть только один рекурсивный вызов. Однако я действительно смущаюсь, когда вижу два или более рекурсивных вызова в одной и той же функции. Пример:

int MaximumElement(int array[], int index, int n)
    {  
        int maxval1, maxval2; 
        if ( n==1 ) return array[index];
        maxval1 = MaximumElement(array, index, n/2); 
        maxval2 = MaximumElement(array, index+(n/2), n-(n/2));
        if (maxval1 > maxval2)
            return maxval1;
        else
            return maxval2;
    }

Я понимаю одну вещь, что n уменьшается наполовину во время каждого рекурсивного вызова. Я просто не понимаю, как работает следующий рекурсивный вызов. Это сбивает с толку и мое понимание, пока этот момент не разваливается, и я сдаюсь. Я был бы очень благодарен, если бы кто-нибудь мог проиллюстрировать это вручную на аккуратном примере. Я уже сделал программирование и распечатал результаты. Однако я не понимаю, как работают расчеты, лежащие в основе этого. Вот мое понимание до момента, когда все сводится к нулю:

интервал [] = {1,2,10,15,16,4,8}

Первоначальный вызов: MaximumElement(a, 0, 7)

Функция начинается: Первый вызов: MaximumElement(a, 0, 7/2) n теперь становится 7/2 = 3

Второй вызов: MaximumElement(2,0,3/2) n теперь становится 3/2 = 1

Базовое условие выполнено, и max1 получает a[0] = 1

Вот где начинается ад: второй рекурсивный вызов начинается с индекса 0 и n = index + n/2 = 0 + 1/2 = 0? Когда я печатаю значения, программа показывает 3 как значение для n при выполнении второго вызова.

Я много программировал, но с этим у меня действительно кошмар. Большое спасибо тому, кто может сломать это для меня!!

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

        public int MAXIMUMELEMENT(int a[], int i, int n)
        {
        int max1, max2;

        System.out.println("1: " + i + " 2: " + n);

        if(n == 1)
        {
            System.out.println("Returning " + a[i]);
        return a[i];
        }



        max1 = MAXIMUMELEMENT(a, i, n/2);

        System.out.println("Index: "+i+" "+" Variable: "+max1+" n value: "+n);


            max2 = MAXIMUMELEMENT(a, i + (n/2), n - (n/2));

        System.out.println("Index2: " + i + " " + "Variable2: " + max2);


        if(max1 > max2)
        {
            System.out.println("Returning.... " + max1 );    
                return max1;
        }
        else
        {
        System.out.println("Returning.... " + max2);     
        return max2;
        }
}

java recursion algorithm divide-and-conquer
person acc_so    schedule 07.10.2013    source источник

Ответы (3)


arrow_upward
19
arrow_downward

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

a = [1,2,10,15,16,4,8]

вы на «верхнем уровне» вычисляете две вещи:

maxval1 = MaximumElement(array, 0, 3); 
maxval2 = MaximumElement(array, 3, 4);

что говорит

  • сделать maxval1 максимальное значение из массива в диапазоне, начиная с индекса 0 размера 3
  • сделать maxval2 максимальное значение из массива в диапазоне от индекса 3 размера 4

So

  • maxval1 действительно будет 10
  • maxval2 действительно будет 16

и ваш ответ будет 16.

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

Я думаю, вы застряли там, где вы сказали, что «всё дерьмо вырвется на свободу», потому что второй рекурсивный вызов начинается с начального индекса 0. Это не так. Он начинается с индекса 3. (То есть, если ваш второй рекурсивный вызов вычисляет maxVal2).

Вот немного сокращенного следа того, как работает ваше вычисление. Я взял на себя смелость переименовать вашу функцию в m и предположить, что maxVal1 и maxVal2 были вычислены более "функционально".

a = [1,2,10,15,16,4,8]

m(a, 0, 7)
= m(m(a, 0, 3), m(a, 3, 4))
= m(m(m(a, 0, 1), m(a, 1, 2)), m(a, 3, 4))
= m(m(a[0], m(a, 1, 2)), m(a, 3, 4))
= m(m(1, m(a, 1, 2)), m(a, 3, 4))
= m(m(1, m(m(a, 1, 1), m(a, 2, 1)), m(a, 3, 4))
= m(m(1, m(a[1], a[2])), m(a, 3, 4))
= m(m(1, m(2, 10)), m(a, 3, 4))
= m(m(1, 10), m(a, 3, 4))
= m(10, m(a, 3, 4))
= …
= 16
person Ray Toal    schedule 07.10.2013
comment
Действительно понятное объяснение! Думаю, теперь я понял и могу начать пытаться понять другие алгоритмы «разделяй и властвуй». Большое спасибо Рэй!! - person acc_so; 07.10.2013
comment
@Ray Toal +1 мне тоже помогло. Спасибо Рэй!! - person code_fish; 07.10.2013
comment
Преимущество рекурсии в том, что вам не нужно беспокоиться о том, чтобы отследить слишком много объектов. Если вы доверяете своему базовому варианту и тому, как вы добираетесь до него, то понимания одного уровня должно быть достаточно. — Эти линии — золото. - person ; 03.09.2019
comment
Это очень информативно. - person Vishwanath Gulabal; 25.07.2021

arrow_upward
9
arrow_downward

Я не уверен, что смогу объяснить это очень хорошо, но вместо этого я объясню это с помощью Фибоначчи. Рекурсивный способ вычисления чисел Фибоначчи:

public static int getFib(int n) {
    if(n <= 2) return 1;
    return getFib(n-1)+getFib(n-2);
}

Что на самом деле происходит в коде, так это то, что он, очевидно, будет выполнять вызовы методов до тех пор, пока не получит первый возврат. Таким образом, getFib(n-1) будет вызываться до n <= 2, затем он вернется к стеку методов, и, поскольку теперь у него есть значение для этого getFib (n-1), он вызовет getFib (n-2). Итак, скажем, наш первоначальный вызов с 4, что происходит:

getFib(4) //Initial call
  getFib(4-1=3) //Left hand recursive call level 1
    getFib(3-1=2) //Left hand recursive call level 2
      return 1 //This would be level 3
    getFib(3-2=1) //Right hand recursive call level 2
      return 1 //level 3
  getFib(4-2=2) //Right hand recursive call level 1
    return 1

Не уверен, что это имеет смысл, это изображение может немного визуализировать это: Рекурсивное дерево Фибоначчи
(источник: fortystones.com)

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

person Alowaniak    schedule 07.10.2013
comment
Это объяснение помогло мне понять это тоже хорошо! Спасибо! - person acc_so; 07.10.2013

arrow_upward
6
arrow_downward

Мне кажется, вы перепутали порядок выполнения рекурсивных вызовов. Имейте в виду, что второй вызов (maxval2) не будет вызван до тех пор, пока не завершится первый вызов (maxval1). Сам вызов maxval1 имеет внутри себя еще два рекурсивных вызова и так далее. Таким образом, без завершения всех этих внутренних рекурсивных вызовов программа не достигает строки maxval2.

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

person Niki    schedule 07.10.2013