2

我在一位教我 C++（作为第一语言）的朋友的指导下编写了递归函数。但是，我真的不明白发生了什么。他帮助我（以及 SO 社区）编写了一个归并排序函数。

std::vector<int> mergeSort(std::vector<int> original)

//code here to create two vectors, farray and sarray, out of the 
//original std::vector<int> original ; each is half the length,
//note: if the size % 2 != 0, sarray takes the odd int

farray = mergeSort(farray);
sarray = mergeSort(sarray);

//code here merges the two into a single, final sorted std::vector

在这个函数中，我分配：

farray = mergeSort(farray);
sarray = mergeSort(sarray);

这里到底发生了什么？它以 farray 和 sarray 作为参数调用 mergeSort 并更改值。mergeSort 递归地执行到自身多远？直到递归函数调用？

4

5 回答 5

16

每次递归调用函数时，它都会有效地复制所需信息的新副本，然后继续。

你可以有一个“无限”重复的程序，即直到它耗尽资源，通常是堆栈空间——这些副本所在的空间。那看起来像

void recur(){
    recur();
}

int main(){
    recur();
    exit(0); /* won't ever really get here.*/
}

显然，这不是很有用，因此您想编写一个对其重复频率有一定限制的程序。这是一个非常简单的程序来管理它：

#include <iostream>
using namespace std;
void recurSome(int count){
    cout << "RecurSome called with " << count << endl;
    if (count > 0){
        recurSome(count-1);
        cout << "Back at " << count << endl;
    }else{
        cout << "Bottom." << endl;
    }
    return;
}

int main(){
    recurSome(10);
    exit(0);  /* now it will get here. */
}

如果您编译并运行它，请说：

bash $ g++ -Wall -o rc recursome.cpp
bash $ ./rc

你会得到结果：

RecurSome called with 10
RecurSome called with 9
RecurSome called with 8
RecurSome called with 7
RecurSome called with 6
RecurSome called with 5
RecurSome called with 4
RecurSome called with 3
RecurSome called with 2
RecurSome called with 1
RecurSome called with 0
Bottom.
Back at 1
Back at 2
Back at 3
Back at 4
Back at 5
Back at 6
Back at 7
Back at 8
Back at 9
Back at 10
bash $

看看它是如何被调用为 10，然后是 9，等等，然后在它到达底部后，它显示它返回 1，然后是 2，等等，直到 10？

基本规则是每个递归函数都应该有一些构成基本情况的东西，一个确实会再次调用自己的东西。在这个例子中，基本情况是count == 0，事实上我们可以把它写成一个递归定义

recursome:
if c = 0 : print bottom
if c > 0 : print count, and recursome(c-1)

当您继续学习数学时，您会看到许多此类递归定义。

这是一个更漂亮的 C 版本，输出更好：

#include <stdio.h>
#include <stdlib.h>

int max = 10;

void recurSome(int count){
    printf("RecurSome %*c Called with %d\n", max-count+1, ' ', count);
    if (count > 0){
        recurSome(count-1);
        printf("RecurSome %*c Back at %d\n", max-count+1, ' ', count);
    }else{
        printf("RecurSome %*c Bottom.\n", 2*max, ' ');
        printf("RecurSome %*c Back at %d\n", max-count+1, ' ', count);
    }
    return;
}

int main(){
    recurSome(max);
    exit(0);  /* now it will get here. */
}

输出：

RecurSome   Called with 10
RecurSome    Called with 9
RecurSome     Called with 8
RecurSome      Called with 7
RecurSome       Called with 6
RecurSome        Called with 5
RecurSome         Called with 4
RecurSome          Called with 3
RecurSome           Called with 2
RecurSome            Called with 1
RecurSome             Called with 0
RecurSome                      Bottom.
RecurSome             Back at 0
RecurSome            Back at 1
RecurSome           Back at 2
RecurSome          Back at 3
RecurSome         Back at 4
RecurSome        Back at 5
RecurSome       Back at 6
RecurSome      Back at 7
RecurSome     Back at 8
RecurSome    Back at 9
RecurSome   Back at 10
于 2009-04-22T21:23:18.510 回答
2

查字典：

递归：名词。见递归

现在，严肃地说，在上面的笑话中，递归的定义是根据递归本身给出的。那就是递归。

递归算法是一种基于算法本身实现的算法。开发这种算法的过程从最基本的情况开始，其解决方案要么是预先知道的，要么可以简单地计算出来。然后根据算法本身来定义算法。

作为一个简单的例子，计算给定整数 i 的 n 次方可以是一个函数power( int number, int power )。你怎么能实现它？很多方面。最简单的是调用库，然后是循环，或者您可以根据自身定义函数：

int power( int number, unsigned int pow )
{
   // Basic trivial case, cuts the recursion:
   if ( pow == 0 ) return 1;

   // Implement power in terms of itself:
   return number * power( number, pow-1 );
}
int main()
{
   int power = power( 2, 10 );
}

我们已经根据自身定义了函数。你从最基本的情况开始（n^0 = 1）。如果我们不是最简单的情况，你可以用它本身来表达你的算法。

该程序将从 main 开始，调用power( 2, 10 )将递归并调用power( 2, 9 )将问题简化为更小的问题，然后根据更简单的问题组成最终答案。

实际的呼叫跟踪将是：

power( 2, 5 )
  power( 2, 4 )
    power( 2, 3 )
      power( 2, 2 )
        power( 2, 1 )
          power( 2, 0 )    // simplest case: return 1
        return 2 * 1 -> 2  // obtain next solution in terms of previous
      return 2 * 2 -> 4
    return 2 * 4 -> 8
  return 2 * 8 -> 16
return 2 * 16 -> 32

在开发递归算法时，它通常帮助我相信我已经启动并运行了算法，并且只需处理新结果的减少/组合。

于 2009-04-22T22:01:24.597 回答
2

递归可以理解为归纳原理的实际应用。为了证明所有 n 的陈述 P(n)，其中 P(n) 表示“从 1 到 n 的整数之和为 n(n+1)/2”，我们必须证明两件事：

  1. 基本情况： P(n) 适用于特定整数。P(1) 为真，因为 1 = 1(1+1)/2。
  2. 归纳案例：如果 P(n) 为真，则 P(n+1) 必须为真。1 + ... + n + (n+1) = n(n+1)/2 + (n+1) = n(n+1)/2 + 2(n+1)/2 = (n+ 1)((n+1)+1)/2，即命题P(n+1)。

同样，在像 mergeSort 这样的递归函数中，我们需要处理两种情况：

  1. 基本情况：如果数组只有一个元素，则排序；除此以外
  2. 递归案例：将数组拆分为两个较小的数组，对每个数组进行mergeSort，然后合并在一起。

关键是这两个数组比原来的要小，否则其中一个永远不会达到基本情况。因为数组被大致分成两半，在这种情况下，递归的深度约为 log2(n)。

就问题中的代码而言，存在三个问题：

  1. 缺少基本情况。
  2. 重用变量 farray 和 sarray 并不是绝对必要的，而且可能会造成混淆。
  3. 由于创建和销毁的 std::vectors 的数量，代码将非常慢。mergeSort 的最佳接口采用两个 vector::iterators 作为输入，类似于 std::sort() 函数。

新程序员应该尝试用纸和铅笔运行mergeSort。

于 2009-04-22T22:52:11.867 回答
0

为了使递归函数不是无限的，需要有一些条件，它返回而不调用自身。对于某些算法，该条件是对数据执行调用不再有意义的点。

在您的情况下，如果您拆分传入的向量并最终得到两个向量，每个向量仅包含 1 个项目，那么对它们调用 mergeSort() 是否有意义？不。

您可以通过检查 farray 和 sarray 的大小并决定在组合它们并返回组合之前是否在其中一个或两个上调用 mergeSort() 来处理这个问题。

如果一个有 2 个项目，一个有 1 个项目怎么办？在尺寸 2 上调用 mergeSort() 但不在尺寸 1 上调用。

当对 mergeSort() 的调用在返回之前没有在 farray 或 sarray 上调用 mergeSort() 时，递归将开始展开。

于 2009-04-22T22:00:50.073 回答
0

查看 wikipedia page for merge sort以获取有关您尝试执行的操作的更多信息。

作为旁注，请注意您正在制作作为参数提供的每个向量的副本。使用 vector<> const& 代替。

于 2009-04-22T22:14:28.637 回答