11

如果函数中只有一个递归调用，我可以很容易地理解递归。但是，当我在同一个函数中看到两个或多个递归调用时，我真的很困惑。例子：

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

3 回答 3

19

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

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
于 2013-10-07T05:37:24.407 回答
10

我不确定我是否能够很好地解释它，但我会用斐波那契来解释它。计算斐波那契数的递归方法是：

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）递归斐波那契树

上面的代码基本上会先深度（先取左孩子）遍历该树。

于 2013-10-07T05:40:50.273 回答
6

在我看来，您混淆了递归调用的运行顺序。请记住，在第一次调用 (maxval1) 完成之前，不会调用第二次调用 (maxval2)。maxval1 调用本身内部还有两个递归调用，依此类推。因此，如果没有完成所有这些内部递归调用，程序就不会到达 maxval2 行。

尝试调试而不是运行代码（例如在 Eclipse 中），并逐步了解每个递归调用的实际情况。

于 2013-10-07T05:40:27.470 回答