所谓函数的递归调用是指在调用一个函数的过程中出现直接或间接调用该函数自身的情况。例如，在调用f1()函数的过程中，又调用了f1()函数，这称为直接递归调用；而在调用f1()函数的过程中，调用了f2()函数，又在调用了f2()函数的过程中调用了f1()函数，这称为间接递归调用。
提到递归调用，最常用的例子就是求一个正整数的阶乘问题。例如，求整数5的阶乘，即5！。由于5！=5*4！，4！=4*3！，… 1!=1*0!,而0!等于1是已知的。于是可求出5！=5*4*3*2*1*1等于120。
由此可见，使用递归调用解决问题的方法如下：
原有的问题能够分解为一个新的问题，而新的问题有用到了原有问题的解法，这就出现了递归。按这一原则分解下去，每次出现的新问题是原问题简化后的子问题，最终分解出来的新问题是一个已知解的问题。这便是递归调用。
一、递归调用的过程
递归调用可分为两个阶段：
- “递推”阶段：将原问题不断分解为新的子问题，逐渐从未知向已知的方向推测，最终到达已知的条件，即递归结束条件，这是递推阶段结束。
- “回归”阶段：该阶段是从已知的条件出发，按照“递推”的逆过程，逐一求值回归，最后到达递推的开始处，结束回归阶段，完成递归调用。
二、递归调用的特点
（1） 递归调用方法编写程序简洁清晰，可读性强；
（2） 递归调用在时间和空间的开销上比较大，既要花费较长的计算时间，又要占用较多的内存单元。
三、递归调用实例
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------（1） 求阶乘
（2） 求前n项的和
（3） Fibonacci函数
（4） 汉诺塔问题
（5） 二叉树遍历
（6） 二叉树的所有路径
1.求阶乘代码：
（2）求前n项的和代码(1+2+3+4+5+6....)#include"iostream" using namespace std; long int fac(int n); int main(){ int n; cout<<"Input a positive integer:"<<endl; cin>>n; long fa=fac(n); cout<<n<<"!="<<fa<<endl; system("pause"); return 0; } long int fac(int n){ long int p; if(n==0) p=1; else p=n*fac(n-1); return p; }#include"iostream" using namespace std; class Recursion { public: Recursion(int x,int y):sum(x),a(y){} void add(){ sum+=a; a++; if(a<=5) { add();//调用自身实现递归 } } public: int sum; int a; }; int main() { Recursion T(0,1); T.add(); cout<<"sum="<<T.sum<<endl; system("pause"); return 0; }（3） Fibonacci函数（斐波那契数列）
斐波那契数列是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
第1项是0，第2项是第一个1，这个数列从第3项开始，每一项都等于前两项之和。
Fibonacci函数的数学表达式为：
Fibonacci函数代码：#include"iostream" using namespace std; long int Fib(int n){ if(n==1) return 0; else if(n==2)return 1; else return Fib(n-1)+ Fib(n-2); } int main() { int n; cout<<"Input a positive integer:"; cin>>n; long int f=Fib( n); cout<<"Fib("<< n<<")="<<f<<endl; system("pause"); return 0; }
（4） 汉诺塔问题
有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：
（1）每次只能移动一个圆盘；
（2）大盘不能叠在小盘上面。
注：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。
汉诺塔问题代码#include <iostream> #include <cstdio> using namespace std; int T=0; //移动的次数 void hannoi (int n, char from, char buffer, char to){ if (n == 1){ cout << "Move disk " << n << " from " << from << " to " << to << endl; T++; } else{ hannoi (n-1, from, to, buffer); cout << "Move disk " << n << " from " << from << " to " << to << endl; T++; hannoi (n-1, buffer, from, to); } } int main() { int n; cout<<"输入圆盘的个数："; cin >> n; hannoi (n, 'A', 'B', 'C'); cout<<"移动的次数："<<T<<endl; system("pause"); return 0; }（5） 二叉树遍历
二叉树有3个基本组成单元：根节点（D）、左子书（L）、右子树（R）。二叉树的遍历分为三种：前(先)序、中序、后序遍历。则先(根)序遍历二叉树的顺序是DLR，中(根)序遍历二叉树的顺序是LDR，后(根)序遍历二叉树的顺序是LRD。还有按层遍历二叉树。这些方法的时间复杂度都是O(n)，n为结点个数。
递归调用遍历二叉树代码：
程序中构造的二叉树如下图所示#include <iostream> #include <cstdio> using namespace std; struct node{ int data; //数据元素 node *left,*right; //指向左子树、右子树 }; class Btree { static int n; static int m; public: node *root; Btree(){ root=NULL; } void create_Btree(int); //构造二叉树 void Preorder(node *); //先序遍历 void inorder(node *); //中序遍历 void Postorder(node *); //后序遍历 void display1() {Preorder(root); cout<<endl;} void display2() {inorder(root);cout<<endl;} void display3() {Postorder(root); cout<<endl;} }; int Btree::n=0; int Btree::m=0; void Btree::create_Btree(int x){ node *newnode=new node; //新建一个节点 newnode->data=x; //节点赋值 newnode->right=newnode->left=NULL;//并且新节点的左右子树为空 if(root==NULL) //根节点是否为空 root=newnode; //根节点是否为空时，根节点为newnode else{ node *back; node *current=root; //将大于根节点的值赋给右子树，小于根节点的数赋给左子树 while(current!=NULL){ back=current; if(current->data>x) current=current->left; else current=current->right; } if(back->data>x) back->left=newnode; else back->right=newnode; } } void Btree::Preorder(node *temp) //这是先序遍历二叉树，采用了递归的方法。 { if(temp!=NULL){ cout<<temp->data<<" "; Preorder(temp->left); Preorder(temp->right); } } void Btree::inorder(node *temp) //这是中序遍历二叉树，采用了递归的方法。 { if(temp!=NULL){ inorder(temp->left); cout<<temp->data<<" "; inorder(temp->right); } } void Btree::Postorder(node *temp) //这是后序遍历二叉树，采用了递归的方法。 { if(temp!=NULL){ Postorder(temp->left); Postorder(temp->right); cout<<temp->data<<" "; } } void main() { Btree A; int array[]={7,4,2,3,15,35,6,45,55,20,1,14,56,57,58}; int k; k=sizeof(array)/sizeof(array[0]); //数组元素个数 cout<<"建立排序二叉树顺序: "<<endl; for(int i=0;i<k;i++){ cout<<array[i]<<" "; A.create_Btree(array[i]); } cout<<endl; cout<<endl<<"先序遍历序列: "<<endl; A.display1(); cout<<endl<<"中序遍历序列: "<<endl; A.display2(); cout<<endl<<"后序遍历序列: "<<endl; A.display3(); system("pause"); }
（6） 二叉树的所有路径
当一个节点的左右子树都为空时,把从根节点到该节点的路径保存在向量中,找到所有的叶子节点就完成了对所有路径的保存.
二叉树所有路径代码：
#include <iostream> #include <cstdio> #include <stdio.h> #include <vector> #include <string> using namespace std; struct node { int data; //数据元素 node *left, *right; //指向左子树、右子树 node() {} node(int val) { this->data = val; this->left = this->right = NULL; } }; class Btree { public: node *root; Btree() { root = NULL; } void create_Btree(int); //构造二叉树 }; class PathsBtree { public: /** * @param root the root of the binary tree * @return all root-to-leaf paths */ vector<string> binaryTreePaths(node* root) { vector<string>Paths; if (root == NULL) return Paths; bTreePathsCore(root, Paths, to_string(root->data)); return Paths; } void bTreePathsCore(node *root, vector<string>&Paths, string strPaths) { if (root->left == NULL&&root->right == NULL) { Paths.push_back(strPaths); return; } if (root->left != NULL) bTreePathsCore(root->left, Paths, strPaths + "->" + to_string(root->left->data)); if (root->right != NULL) bTreePathsCore(root->right, Paths, strPaths + "->" + to_string(root->right->data)); } }; void Btree::create_Btree(int x) { node *newnode = new node; //新建一个节点 newnode->data = x; //节点赋值 newnode->right = newnode->left = NULL;//并且新节点的左右子树为空 if (root == NULL) //根节点是否为空 root = newnode; //根节点是否为空时，根节点为newnode else { node *back=NULL; node *current = root; //将大于根节点的值赋给右子树，小于根节点的数赋给左子树 while (current != NULL) { back = current; if (current->data>x) current = current->left; else current = current->right; } if (back->data>x) back->left = newnode; else back->right = newnode; } } void main() { Btree A; int array[] = { 7,4,2,3,15,35,6,45,55,20,1,14,56,57,58 }; int k; k = sizeof(array) / sizeof(array[0]); //数组元素个数 cout << "建立排序二叉树顺序: " << endl; for (int i = 0; i<k; i++) { cout << array[i] << " "; A.create_Btree(array[i]); } PathsBtree pa; vector<string> path=pa.binaryTreePaths(A.root); for (int i = 0; i < path.size();i++) { cout <<"root-to-leaf path "<<(i+1)<<":"<< path.at(i) << endl; } system("pause"); }参考资料：http://www.cnblogs.com/elleniou/archive/2012/05/03/2480042.html
http://www.cricode.com/3489.html
http://blog.csdn.net/fanglegefang/article/details/70477509
所谓递归-recursive就是可以在方法里自己调用自己。
以下是一个最简单的递归（当然会是死循环，所以真正的递归不要这样写）
public void sayHi(){
System.out.println(“Hello!”);
sayHi(); //自己调用自己，会无数次的调用
}
以上的这个程序如果你运行的话，最终会StackOverFlow也就是堆栈溢出错误真正的递归应用之一：求某个数的阶乘
public int fact(int n){
if(n>0)
return n*fact(n-1);
else
return 1;
}
假如参数是4它的调用顺序如下图1所示：
图1-递归调用示意图
int strlen（char *p） // 注意！ 不允许定义任何变量
{
if( *p )
return strlen（p + 1）+ 1;
return 0;
}int strlen(char* p, int add_num=0){return '/0'==*p?add_num:strlen(p+1, add_num+1);}用strlen()计算字符串的长度不包括'/0'已知 char *str1="absde";
char str2[]="absde";
char str3[8]={'a',};
char ss[] = "0123456789";sizeof(str1)=4;sizeof(str2)=6;
sizeof(str3)=8;
sizeof(ss)=11总之，对于指针，sizeof操作符返回这个指针占的空间，一般是4个字节；而对于一个数组，sizeof返回这个数组所有元素占的总空间。char*与char[]容易混淆，一定要分清，而且而strlen不区分是数组还是指针，就读到/0为止返回长度。而且strlen是不把/0计入字符串的长度的。char a[]="abc/0efg";
printf("%d",strlen(a)); ///3 遇 '/0'结束
printf("%d",sizeof(a)); ///8 只是一个操作符strlen和sizeof的区别：sizeof在编译器求解，strlen在运行期求解，这是主要区别其次strlen只能求C风格字符串长度sizeof()可以求很多类型的大小是否计算'/0'
根据这一简单的事例，可以帮助初学者理解递归。
例6.28 已知一个一维数组A[1..N](N<50)，又已知一整数M。 如能使数组A中任意几个元素之和等于M，则输出YES，反之则为NO。
结合例题对该问题的分析,根据左边给出的输入数据完成下列递归调用示意图的填空部分.
————————————答案————————————————
——————————————————————————————————————————
——————————————————答案——————————————————————
转载于:https://www.cnblogs.com/vacation/p/5178447.html
递归函数：一个含直接或间接调用本函数语句的函数被称之为递归函数。
在很多的编程实例中都会用到递归的方式解决问题，在许多问题上使用递归的思想解题也会非常方便。使用递归调用的代码可读性高，易于理解。就拿斐波那契数列为列，在初学编程时应该都使用过递归求斐波那契数列吧。递归的实例还有很多，如我们的汉诺塔问题，构建二叉树等等。相信现在让大家用递归写一个递归求阶乘什么的都分分钟可以解决，递归嘛，简单的很。可是…你真的有了解过递归吗？
今天我们的主题是，递归调用的几种传值方式，以及几个简单的递归调用图分析。
下面进入正题。
文章目录
1. 函数形参的几种传值方式比较
在我们C/C++语言中，有几种特殊的传值方式。例如一个
int fun(int n)的函数，我们就有以下几种常用的传值方式。定义：int n = 10;。
此外，还有一种特殊的传值方式，那就是C++中的引用传递。int fun(int& n) 、int n = 10 。
这几种传值方式，在一般的函数中都基本不会出现什么问题。但是，如果把他们用在了递归函数中那可就不一样了。
示范：如斐波那契数列递归式
int Fib(int n)
{
if (n <= 2) return 1;
else return Fib(n - 1) + Fib(n-2);
}
int main() { Fib(5); return 0; }
其五次的递归调用图为：
请参考示范完成下列各示例。
参考代码：
void fun1(int i, int n)
{
if (i >= n)
{
}
else
{
fun1(i + 1, n);
fun1(i + 1, n);
}
}
int main()
{
fun1(0,3);
return 0;
}
请认真思考其调用过程，并画出他们的递归调用图。
参考代码：
void fun2(int i, int n)
{
if (i >= n)
{
}
else
{
fun2(++i, n);
fun2(++i, n);
}
}
int main()
{
fun2(0,3);
return 0;
}
请认真思考其调用过程，并画出他们的递归调用图。
参考代码：
void fun3(int &i, int n)
{
if (i >= n)
{
}
else
{
fun3(++i, n);
fun3(++i, n);
}
}
int main()
{
int a = 0;
fun3(a,3);
return 0;
}
请认真思考其调用过程，并画出他们的递归调用图。
参考代码：
void fun4(int i, int n)
{
if (i >= n)
{
}
else
{
fun4(i++, n);
fun4(i++, n);
}
}
int main()
{
fun4(0,3);
return 0;
}
请认真思考其调用过程，并画出他们的递归调用图。
通过分析递归结构我们可以知道该段代码在运行时的调用可以看做是一个二叉树。
这里我们在每次递归调用时，打印 i 的值，分析调用过程。这里输出的 i 的序列是对其进行前序二叉遍历的结果。
void fun1(int i, int n)
{
cout << i << " " ;
if (i >= n)
{
}
else
{
fun1(i + 1, n);
fun1(i + 1, n);
}
}
// 输出：0 1 2 3 3 2 3 3 1 2 3 3 2 3 3
// 以下用每层调用时i的值，分析递归调用过程
// 0
// / \
// 1 1
// / \ / \
// 2 2 2 2
// /\ /\ /\ /\
// 3 3 3 3 3 3 3 3
void fun2(int i, int n)
{
cout << i << " " ;
if (i >= n)
{
}
else
{
fun2(++i, n);
fun2(++i, n);
}
}
// 输出：0 1 2 3 4 3 2 3 4
// 以下用每层调用时i的值，分析递归调用过程
// 0
// / \
// 1 2
// / \ / \
// 2 3 3 4
// /\
// 3 4
void fun3(int &i, int n)
{
cout << i << " " ;
if (i >= n)
{
}
else
{
fun3(++i, n);
fun3(++i, n);
}
}
// 输出：0 1 2 3 4 5 6
// 以下用每层调用时i的值，分析递归调用过程
// 0
// / \
// 1 6
// / \
// 2 5
// /\
// 3 4
void fun4(int i, int n)
{
cout << i << " ";
if (i >= n)
{
}
else
{
fun4(i++, n);
fun4(i++, n);
}
}
// 输出：0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... ...
// 以下用每层调用时i的值，分析递归调用过程
// 0
// /
// 0
// /
// 0
// /
// 0
// /
// 0
// ...
这里主要对引用传递 和 i++ 传递进行分析。
void fun3(int &i, int n) 引用传递的参数与原参数实际上是一个变量。可以认为引用传递的参数对整个函数是全局作用域的，在函数内参数改变时，将会对整个函数产生影响。fun4(i++) ，这种传值方式等同于为 fun4(n) 。这就形成了死递归，而递归函数严格意义上来说并没有无限递归、死递归的说法。因为，递归调用时在栈上开辟空间，而栈的大小是有限制的，当我们程序说使用的栈空间超过了栈的容量时就会发生栈溢出错误。我这里使用的 vs 编译器，经测试栈空间大小约为 1M左右，在 Centos 7 下测试栈空间约为 8M 左右。既然我们已经分析出了他的调用过程，不妨再设计程序打印出其调用过程的树形结构图。
首先，定义一个结点，保存树的结点深度和结点值
struct node // 保存树的结点
{
node(int _dep, int _val) :dep(_dep), val(_val)
{}
int dep; // 根节点的深度
int val; // 根节点的数值
};
其次，定义“打印树”类，主要数据成员有 left和right ，分别保存树的左右子树结点。以及增加左右子树的方法和一个输出树结构的方法。
class PrintTree
{
public:
void addLeft(node tmp)
{
left.push_back(tmp);
}
void addRight(node tmp)
{
right.push_back(tmp);
}
void showTree(int depth);
private:
vector<node> left;
vector<node> right;
};
实现输出树结构层次的方法，这里要借助一个“数的深度”参数来实现，打印相同深度的结点。另外，为了让输出的“树形”更直观，我们再根据树的深度不同打印数量不同的空格。
void PrintTree::showTree(int depth)
{
cout << "\t0" << endl; // 根节点
int i = 1;
while (i <= depth)
{
vector<node>::const_iterator lt = left.begin();
vector<node>::const_iterator rt = right.begin();
int sp = depth - i; /* 打印空格 */
while (sp-- ){ cout << " ";}
while (lt<left.end())
{
if ((*lt).dep == i) /* 输出深度为 i 的左结点 */
{
cout << (*lt).val ;
int s = depth - i+1; /* 打印空格 */
while (s--) { cout << " "; }
}
lt++;
}
while (rt < right.end()) /* 输出深度为 i 的右结点 */
{
if ((*rt).dep == i)
{
cout << (*rt).val ;
int s = depth - i +1; /* 打印空格 */
while (s--) { cout << " "; }
}
rt++;
}
cout << endl;
i++;
}
}
最后，改造三个递归函数，使之在递归调用时把结点信息存入“打印树”中。
void fun11(int i, int n, PrintTree& t)
{
if (i >= n)
{
}
else
{
t.addLeft(node(i + 1, i + 1));
fun11(i + 1, n, t);
t.addRight(node(i + 1, i + 1));
fun11(i + 1, n, t);
}
}
void fun22(int i, int n,PrintTree& t,int d)
{
if (i >= n)
{
}
else
{
int k = i;
t.addLeft(node(d + 1, ++k));
fun22(++i, n, t, d + 1);
t.addRight(node(d + 1, ++k));
fun22(++i, n, t, d + 1);
}
}
void fun33(int& i, int n, PrintTree& t, int d)
{
if (i >= n)
{
}
else
{
t.addLeft(node(d + 1, i+1));
fun33(++i, n,t,d+1);
t.addRight(node(d + 1, i+1));
fun33(++i, n,t,d+1);
}
}
run：fun11();
int main()
{
PrintTree tr;
fun11(0, 3, tr);
tr.showTree(3);
return 0;
}
// 输出：
0
1 1
2 2 2 2
3 3 3 3 3 3 3 3
run：fun22();
int main()
{
PrintTree tr;
fun22(0, 3, tr, 0);
tr.showTree(3);
return 0;
}
// 输出
0
1 2
2 3 3 4
3 4
run：fun33();
int main()
{
PrintTree tr;
int a = 0;
fun33(a, 3, tr, 0);
tr.showTree(3);
return 0;
}
// 输出
0
1 6
2 5
3 4
