了解双重递归

  • Z时代
  • 2024-01-10
  • 分类：问答

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

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

int a [] = {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 =索引+ 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;
        }
}

回答：

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

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

您是在“顶级”计算两件事：

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

这说

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

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

所以

  • 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

以上是 了解双重递归 的全部内容， 来源链接： utcz.com/qa/427471.html

回到顶部