c++ - 在 C++ 中递归执行到你的函数有多远？

Question

我在教我 C++(作为第一语言)的 friend 的指导下编写了递归函数。但是，我真的不明白发生了什么。他帮助我(以及 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 递归执行多远？只是递归函数调用？

Answer 1

每次递归调用函数时，它都会有效地制作一份所需信息的新拷贝，然后继续。

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

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