C++ 函数中递归执行了多远？
https://stackoverflow.com/questions/779282
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我在一位教我 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。事实上，我们可以写此作为递归定义
recursome：结果 如果c = 0：打印底部，点击 如果c> 0：打印计数，和recursome（C-1）
您会看到诸如此类的许多递归定义，你在数学上移动
这里的更好的输出稍微niftier 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
其他提示
检查出来在字典中：
<强>递归：名词。参见递归
现在，作为严重，在上面的玩笑，递归的定义在递归本身来给出。即递归。
一个递归算法是一种算法，其实现是基于算法本身。开发这样的算法的过程开始于最基本的情况下，其溶液是预先已知的，或者可以被平凡计算。然后，你在其本身来定义的算法。
作为简单的示例，在计算一个给定的整数的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）。如果我们不是在简单的情况下，您可以用自身的表达你的算法。
该计划将启动在主要通过调用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
在开发递归算法通常让我相信我已经有算法和运行，只是在新的结果进行还原/合成工作。
递归可以理解为归纳原理的实际应用。为了证明所有 n 的陈述 P(n)，其中 P(n) 意味着“从 1 到 n 的整数之和是 n(n+1)/2”，我们必须证明两件事：
- 基本情况： P(n) 对于特定整数成立。P(1) 为真，因为 1 = 1(1+1)/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 这样的递归函数中，我们需要处理两种情况：
- 基本情况： 如果数组只有一个元素，则它已排序；否则
- 递归情况： 将数组拆分为两个较小的数组，对每个数组进行合并排序，然后将它们合并在一起。
关键是这两个数组是 较小 比原来的要好，否则其中之一永远不会达到基本情况。由于数组大致分为两半，因此在这种情况下递归的深度约为 log2(n)。
就问题中的代码而言，存在三个问题：
- 基本情况缺失。
- 重用变量 farray 和 sarray 并不是绝对必要的，而且可能会造成混乱。
- 由于创建和销毁的 std::vector 数量较多，代码将非常慢。mergeSort 的最佳接口采用两个向量::迭代器作为输入，类似于 std::sort() 函数。
新程序员应该尝试用纸和笔运行合并排序。
有关一个递归函数来不可能是无限的，需要有一些条件，其中它返回而不调用本身。对于一些算法，该条件是其对数据进行通话不再有意义的点。
在你的情况下，如果拆分传入向量和结束两个向量，每个只包含1项，是否有意义呼吁他们归并（）？号
您可以通过检查farray和sarray的大小，决定是否将它们结合起来，并在返回前组合上的一个或两个调用归并（）处理这个问题。
如果一个有2个项目和一个具有1？上的尺寸2调用归并（），但不是在尺寸1。
当于归并（）的调用不返回之前在任farray或sarray调用归并（），递归将开始退绕。
有一个在维基百科页面排序合并更多的信息，你”重新尝试做的。
作为一个旁注，要知道，你让你给出一个参数每载体的拷贝。使用矢量<>常量＆代替。
