递归在C++中执行到函数的程度是多少？

Question

我在一位教我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以递归方式执行多长时间？刚到递归函数调用？

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:
如果c = 0:
如果c> 0则打印底部:打印计数和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