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)，即递推公式.所以这个递归函数不难书写
#includeusing namespace std;
int F(int n)//函数返回⼀个数对应的Fibonacci数{ if(n0 || n1)//递归边界
return 1; return F(n-1) + F(n-2);//递归公式}
int main(){ //测试
int n; while(cin >> n) cout << F(n) << endl;
return 0;
}
2.阶乘阶乘的递归公式为：
代码如下：
#includeusing 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⼿动求和的过程是什么？步骤如下：
c语言用递归函数求n的阶乘x+y=a，任务变为a,z,w求和
a+z=b，任务变为b,w求和
b+w=c得出答案
思考⼀下，【得出答案】这⼀步为什么就可以得出答案呢？(废话？)是因为，⼀个数不⽤相加就能得出答案.
所以，递归的边界就是只有⼀个数.
所以，递归边界有了，那么递归公式呢？其实⼿动计算过程中，隐含了递归公式：
其中+为求两个数的和，F为求多个数的和的递归函数.代码如下：
#includeusing 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为求多个数的最⼤值的递归函数.代码如下：
#includeusing 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++的⼩伙伴可以+⼊学习。最后祝所有程序员都能够⾛上⼈⽣巅峰，让代码将梦想照进现实，⾮常适合新⼿学习，有不懂的问题可以随时问我，⼯作不忙的时候希望可以给⼤家解惑
赞(0)回复(1)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。