c++ - 循环内的尾递归如何工作？

Question

我正在尝试理解递归，而且我对递归还很陌生。考虑上面给出的示例，在 for 循环中有一个递归调用。

程序是:

#include <iostream>
#include <string.h>
#define n 2
using namespace std;
int k = 0;
void nontailrec(int x) {
if(x == n) {
    return;
}
for(int i = 0 ; i < n ; i++) {
    cout<< i << " "<< x <<endl;
    nontailrec(x+1);
}
}
int main() {
nontailrec(k);
return 0;
}

现在了解程序的流程，我得出的流程是:

main();
nontailrec(0);
0 == 2 ?
<<0 0
nontailrec(1);
1 == 2 ?
<<0 1             
nontailrec(2);    
2 == 2 ?           
return void            
<<1 1
<<1 0

end of program

但实际输出是:

0 0
0 1
1 1
1 0
0 1
1 1

代替

0 0
0 1
1 1
1 0

最后两行输出是怎么来的，程序的具体流程是什么？

Answer 1

递归函数与非递归函数完全一样。
特别是，return 不会返回到初始的顶级调用，只会返回到直接调用者。
也就是说，终止递归不像退出循环。

假设每个 x 都有一个唯一的函数，您的程序将等同于此:

void nontailrec_2() {
}

void nontailrec_1() {
    for(int i = 0 ; i < n ; i++) {
        cout<< i << " "<< 1 <<endl;
        nontailrec_2();
    }
}

void nontailrec_0() {
    for(int i = 0 ; i < n ; i++) {
        cout<< i << " "<< 0 <<endl;
        nontailrec_1();
    }
}

int main()
{
    nontailrec_0();
}

我相信您可以按照流程进行操作。