理解双递归 [英] Understanding double recursion

问题描述

如果函数中只有一个递归调用，我就能轻松理解递归。但是，当我在同一个函数中看到两个或多个递归调用时，我真的很困惑。示例：

I'm able to comprehend recursion easily if there is just one recursive call within a function. However, I am really getting confused when I see two or more recursive calls within the same function. Example:

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减少一半的事情。我只是不明白下一个递归调用是如何工作的。它变得混乱和我的理解，直到那一点崩溃，我放弃了。如果有人可以用一个简洁的例子手动说明这一点，我将非常感激。我已经完成了编程，并打印了输出。但是，我不明白这项工作背后的计算方式。这是我的理解，直到一切都变得一无所获：

I understand one thing that n gets decremented by half during each recursive call. I just don't understand how the next recursive call works. It gets confusing and my understanding until that point falls apart and I give up. I would be really thankful if somebody could please illustrate this manually with a neat example. I already did the programming, and printed the outputs. However, I don't understand how the calculations behind this work. Here is my understanding until the point where everything gets to nothing:

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

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

初始调用：MaximumElement（a，0,7）

Initial call: MaximumElement(a, 0, 7)

该函数开始：
首次调用： MaximumElement（a，0,7 / 2）
n现在变为7/2 = 3

The function begins: First call: MaximumElement(a, 0, 7/2) n now becomes 7/2 = 3

第二次调用：MaximumElement（2,0,3 / 2）
n现在变为3/2 = 1

Second Call: MaximumElement(2,0,3/2) n now becomes 3/2 = 1

满足基本条件且max1得到[0] = 1

The base condition is met and the max1 gets a[0] = 1

这里是所有地狱破裂的地方：
第二次递归调用从索引0开始，n =索引+ n / 2 = 0 + 1/2 = 0？当我打印值时，程序在第二次调用时显示3作为n的值。

Here is where all hell breaks loose: The second recursive call begins with index 0 and n = index + n/2 = 0 + 1/2 = 0? When I print the values the program shows 3 as the value for n when the second call is being made.

我已经进行了大量编程，但我真的有一个噩梦这个。非常感谢有人可以为我解决这个问题!!

I have programmed extensively, but I am really having a nightmare with this. Many thanks to somebody that can break this down for me!!

这是上面的伪代码，但是我在下面看到的java代码（它可能会让它变得更容易）如果你想尝试运行它：）

That was the pseudocode above, but see below for the java code I wrote (it might make it easier for you if you are trying to run it):

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

推荐答案

它听起来你已经理解了基本情况并知道递归是如何工作的，所以理解你的特定例子的关键是要注意给定初始数组

It sounds like you already understand the base case and know how recursion works, so the key to understanding your particular example is to note that given the initial array

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

你是在顶层计算两件事：

you are, at the "top level" computing two things:

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

表示

• make maxval1 从大小为3的索引0开始的范围内数组的最大值


• make maxval2 数组中大小为4的索引3范围内的最大值

• make maxval1 the maximum value from the array in the range starting from index 0 of size 3
• make maxval2 the maximum value from the array in the range from index 3 of size 4

所以

• maxval1 确实是10


• maxval2 确实是16

• maxval1 will indeed be 10
• maxval2 will indeed be 16

，你的答案是16。

关于递归的好处是你不必担心过于广泛地追踪事物。如果你相信你的基本案例以及你得到基本案例的方式，那么理解一个级别就足够了。

The nice thing about recursion is that you don't have to worry about tracing things too extensively. If you trust your base case and the manner in which you get to your base case, then understanding one level should suffice.

我认为你被困在你所说的所有地狱破裂因为第二次递归调用以起始索引0开始。它没有。它从索引3开始。（也就是说，假设你的第二个递归调用是一个计算 maxVal2 ）。

I think you got stuck where you said "all hell breaks loose" because the second recursive call begins with a starting index of 0. It doesn't. It starts at index 3. (That is, assuming your second recursive call is the one computing maxVal2).

这里有一些关于计算如何运作的缩略图。我冒昧地将你的函数重命名为 m 并假设 maxVal1 和 maxVal2 计算得更多功能性。

Here is a bit of an abbreviated trace of how your computation works out. I've taken the liberty to rename your function to m and to assume that maxVal1 and maxVal2 were computed a little more "functionally".

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

这篇关于理解双递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！