c语言递归算法及经典递归例子代码实现

一个过程或变量在其定义或表明中有直接或间接调用自身的一种方法；递归函数就是直接或间接调用自身的变量，也就是自身调用自己；

刚接触递归的朋友，可能无法理解递归，难以理解的点也许这些，例如：

1.函数为什么可以在自己的外部既调用自己呢?

2.既然可以自己调用自己，那么递归运行过程中必定回有很多层相互嵌套，到底什么时候不再嵌套呢？

3.递归运行过程中，相互嵌套的多层之间会有参数传递，多层之间能否会相互影响？

1.递归边界

2.递归的逻辑——递归"公式"

递归的过程一定有参数的差异，并且参数的变化递归算法经典实例，和递归边界有关系.

在难度较大的题目中，这二者均不容易直接得到.

递归的种种困惑，也许理解的朋友可能可以用一句话解释明白，但是不理解的朋友再如何说也没办法理解.

下面通过几个简单的事例【体会】一下递归，先从【感性】的视角理解递归.

1.Fibonacci数

我们直到Fibonacci数的递推公式为：F(0)=F(1)=1,F(n)=F(n-1)+F(n-2) n>=2;

这个明显地给出了数组边界n=0或1的之后F(n)的值，和异或逻辑F(n)=F(n-1)+F(n-2)，即递推公式.所以这个递归函数不难书写

#include<iostream>using namespace std; 
int F(int n)//函数返回一个数对应的Fibonacci数{	if(n==0 || n==1)//递归边界
		return 1;	return F(n-1) + F(n-2);//递归公式} 
int main(){	//测试
	int n;	while(cin >> n)		cout << F(n) << endl; 
	return 0;
}

2.阶乘阶乘的递归公式为：

代码如下：

#include<iostream>using namespace std; 
int F(int n){	if(n==0)//递归边界
		return 1; 
	return n*F(n-1);//递归公式} 
int main(){	int n;	cin >> n;	cout << F(n) << endl; 
	return 0;
}

3.数组求和

给一个数组a[]:a[0],a[1],...,a[n-1]如何用递归的方法求和？

仍然是两个问题：递归边界跟递归公式.

递归边界是哪个？一时不容易想到，但是我们想到了求和，多个数的求和过程是哪个，x,y,z,w手动求和的过程是哪个？步骤如下：

x+y=a,任务变为a,z,w求和

a+z=b,任务变为b,w求和

b+w=c得出答案

思考一下，【得出答案】这一步为什么就可以得出答案呢？(废话？)是因为，一个数不用相加就能得出答案.

所以，递归的边界就是只有一个数.

所以，递归边界有了，那么递归公式呢？其实手动计算过程中，隐含了递归公式：

其中+为求两个数的跟，F为求多个数的跟的递归函数.代码如下：

#include<iostream>using namespace std; 
int F(int a[],int start,int end){	if(start==end)//递归边界
		return a[start]; 
	return a[start] + F(a,start+1,end);//递归公式} 
int main(){	int a[] = {1,2,3,4,5};	int s=0,e=4;	cout << F(a,s,e) << endl; 
	return 0;
}

4.求数组元素最大值

手动求最大值的过程是哪个，遍历+比较，过程如下：

例如，求3,2,6,7,2,4的最大值：先设定最大值max=-999999，然后将max和数组元素逐个(遍历)比较如果a[i]>max，则升级max的值为a[i]，否则max不变，继续向后遍历，直到遍历结束.

max<3，则max=3

max>2，max=3不变

max<6，则max=6

max<7，则max=7

max>2，max=7不变

max>4，max=7不变

遍历结束，max=7为最大值.

和求和类似，递归的推导如下：

其中max为求两个数的较大值变量，F为求多个数的最大值的递归函数.代码如下：

#include<iostream>using namespace std; 
#define max(a,b) (a>b?a:b)
 int F(int a[],int s,int e){	if(s==e)		return a[s];	else if(s+1 == e)//递归边界
		return max(a[s],a[e]); 
	return max(a[s],F(a,s+1,e));//递归公式!!!} 
int main(){	int a[] = {5,1,4,6,2};	int s = 0,e = 4;	cout << F(a,s,e) << endl; 
	return 0;
}

之所以，说里面的几个例子是【简单示例】，是因为上述所有的递归都属于【单向递归】.单向递归，递归的模式就是一个方向，所以模式相对非常容易想到.

较难的递归问题，一般都不是单向递归，而是应该使用【回溯】的方式，递归的技巧不太容易想到.一、什么叫做递归？

一个过程或变量在其定义或表明中有直接或间接调用自身的一种方法；递归函数就是直接或间接调用自身的变量，也就是自身调用自己；

刚接触递归的朋友，可能无法理解递归，难以理解的点也许这些，例如：

1.函数为什么可以在自己的外部既调用自己呢?

2.既然可以自己调用自己，那么递归运行过程中必定回有很多层相互嵌套，到底什么时候不再嵌套呢？

3.递归运行过程中，相互嵌套的多层之间会有参数传递，多层之间能否会相互影响？

1.递归边界

2.递归的逻辑——递归"公式"

递归的过程一定有参数的差异，并且参数的变化，和递归边界有关系.

在难度较大的题目中，这二者均不容易直接得到.

递归的种种困惑，也许理解的朋友可能可以用一句话解释明白，但是不理解的朋友再如何说也没办法理解.

下面通过几个简单的事例【体会】一下递归递归算法经典实例，先从【感性】的视角理解递归.

1.Fibonacci数

我们直到Fibonacci数的递推公式为：F(0)=F(1)=1,F(n)=F(n-1)+F(n-2) n>=2;

这个明显地给出了数组边界n=0或1的之后F(n)的值，和异或逻辑F(n)=F(n-1)+F(n-2)，即递推公式.所以这个递归函数不难书写

#include<iostream>using namespace std; 
int F(int n)//函数返回一个数对应的Fibonacci数{	if(n==0 || n==1)//递归边界
		return 1;	return F(n-1) + F(n-2);//递归公式} 
int main(){	//测试
	int n;	while(cin >> n)		cout << F(n) << endl; 
	return 0;
}

2.阶乘阶乘的递归公式为：

代码如下：

#include<iostream>using namespace std; 
int F(int n){	if(n==0)//递归边界
		return 1; 
	return n*F(n-1);//递归公式} 
int main(){	int n;	cin >> n;	cout << F(n) << endl; 
	return 0;
}

3.数组求和

给一个数组a[]:a[0],a[1],...,a[n-1]如何用递归的方法求和？

仍然是两个问题：递归边界跟递归公式.

递归边界是哪个？一时不容易想到，但是我们想到了求和，多个数的求和过程是哪个，x,y,z,w手动求和的过程是哪个？步骤如下：

x+y=a,任务变为a,z,w求和

a+z=b,任务变为b,w求和

b+w=c得出答案

思考一下，【得出答案】这一步为什么就可以得出答案呢？(废话？)是因为，一个数不用相加就能得出答案.

所以，递归的边界就是只有一个数.

所以，递归边界有了，那么递归公式呢？其实手动计算过程中，隐含了递归公式：

其中+为求两个数的跟，F为求多个数的跟的递归函数.代码如下：

#include<iostream>using namespace std; 
int F(int a[],int start,int end){	if(start==end)//递归边界
		return a[start]; 
	return a[start] + F(a,start+1,end);//递归公式} 
int main(){	int a[] = {1,2,3,4,5};	int s=0,e=4;	cout << F(a,s,e) << endl; 
	return 0;
}

4.求数组元素最大值

手动求最大值的过程是哪个，遍历+比较，过程如下：

例如，求3,2,6,7,2,4的最大值：先设定最大值max=-999999，然后将max和数组元素逐个(遍历)比较如果a[i]>max，则升级max的值为a[i]，否则max不变，继续向后遍历，直到遍历结束.

max<3，则max=3

max>2，max=3不变

max<6，则max=6

max<7，则max=7

max>2，max=7不变

max>4，max=7不变

遍历结束，max=7为最大值.

和求和类似，递归的推导如下：

其中max为求两个数的较大值变量，F为求多个数的最大值的递归函数.代码如下：

#include<iostream>using namespace std; 
#define max(a,b) (a>b?a:b)
 int F(int a[],int s,int e){	if(s==e)		return a[s];	else if(s+1 == e)//递归边界
		return max(a[s],a[e]); 
	return max(a[s],F(a,s+1,e));//递归公式!!!} 
int main(){	int a[] = {5,1,4,6,2};	int s = 0,e = 4;	cout << F(a,s,e) << endl; 
	return 0;
}

之所以，说里面的几个例子是【简单示例】，是因为上述所有的递归都属于【单向递归】.单向递归，递归的模式就是一个方向，所以模式相对非常容易想到.

较难的递归问题，一般都不是单向递归，而是应该使用【回溯】的方式，递归的技巧不太容易想到.

写在最后

每天晚上20:00我就会开直播给你们免费分享C/C++学习常识和路线途径，C/C++交流学习群:814974917，邀请码：洋洋。群里会不定期更新最新的教程和学习方法（进群送2018最新C/C++学习教程），大家都是学习C/C++的，或是转行，或是大学生，还有工作中想提高自己素质的C/C++党，如果你是正在学习C/C++的小伙伴可以+入学习。最后祝所有程序员都无法走上人生巅峰，让代码将梦想照进现实，非常合适新手学习，有不懂的困惑可以随时问我，工作不忙的之后期望可以帮你们解惑

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-136144-1.html