递归在C ++中执行到您的函数的距离有多远? [英] How far does recursion execute into your function in C++?
问题描述
我已经在一个教我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递归执行到自身的距离有多远?只是递归函数调用?
每次递归调用函数时，它都会有效地复制所需的信息，然后继续.
您可以拥有一个无限次"重复出现的程序，即直到它用完资源(通常是堆栈空间)(这些副本将在其中运行的空间)用完为止.看起来像
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，实际上我们可以将其写为递归定义
递归:
如果c = 0:打印底部
如果c> 0:打印计数，并递归(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
I've written recursive functions with the guidance of a friend who is teaching me C++ (as a first language). However, I don't really understand what is going on. He helped me (and the SO community, as well) write a merge sort function.
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
In this function, I assign:
farray = mergeSort(farray);
sarray = mergeSort(sarray);
What exactly is happening here? It calls mergeSort with farray and sarray as parameters and changes the value. How far does mergeSort execute into itself recursively? Just upto the recursive function call?
Each time you call a function recursively, it effectively makes a new copy of the information it needs, and goes on.
You could have a program that recurs "infinitely", ie, until it runs out of resources, usually stack space — the space in which those copies are going. That would look like
void recur(){
recur();
}
int main(){
recur();
exit(0); /* won't ever really get here.*/
}
Obviously, this isn't very useful, so you want to write a program that has some limit on how often it recurs. Here's a really simple program that manages that:
#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. */
}
If you compile and run that, say with:
bash $ g++ -Wall -o rc recursome.cpp
bash $ ./rc
You'll get the results:
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 $
See how it gets called for 10, then 9, and so on, and then after it reaches the bottom, it shows it coming back for 1, then 2, and so on back up to 10?
The basic rule is that every recursive function should have something that makes a base case, one which does call itself again. In this one, the base case is count == 0 and in fact we could have written this as a recursive definition
recursome:
if c = 0 : print bottom
if c > 0 : print count, and recursome(c-1)
You'll see many recursive definitions of that sort as you move on in math.
Here's a somewhat niftier C version with better output:
#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. */
}
Output:
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
这篇关于递归在C ++中执行到您的函数的距离有多远?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
