c語(yǔ)言有哪些遞歸函數(shù)的例子？

c語(yǔ)言有哪些遞歸函數(shù)的例子？

c語(yǔ)言遞歸函數(shù)的例子：

遞歸就是一個(gè)過(guò)程或 函數(shù) 在其定義或說(shuō)明中有直接或間接調(diào)用自身的一種方法；遞歸函數(shù)就是直接或間接調(diào)用自身的函數(shù)，也就是自身調(diào)用自己的過(guò)程。

1.Fibonacci數(shù)

我們直到Fibonacci數(shù)的遞推公式為：F(0)=F(1)=1,F(n)=F(n-1)+F(n-2) n>=2;

這個(gè)明顯地給出了遞歸邊界n=0或1的時(shí)候F(n)的值，和遞歸邏輯F(n)=F(n-1)+F(n-2)，即遞推公式.所以這個(gè)遞歸函數(shù)不難書(shū)寫(xiě)

#includeusing namespace std; int F(int n)//函數(shù)返回一個(gè)數(shù)對(duì)應(yīng)的Fibonacci數(shù){ if(n0 || n1)//遞歸邊界 return 1; return F(n-1) + F(n-2);//遞歸公式} int main(){ //測(cè)試 int n; while(cin >> n) cout << F(n) << endl; return 0; }

2.階乘的遞歸公式：n*F(n-1)

代碼如下：

#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.數(shù)組求和

給一個(gè)數(shù)組a[]:a[0],a[1],…,a[n-1]如何用遞歸的方式求和？

仍然是兩個(gè)問(wèn)題：遞歸邊界和遞歸公式.

遞歸邊界是什么？一時(shí)不容易想到，但是我們想到了求和，多個(gè)數(shù)的求和過(guò)程是什么，x,y,z,w手動(dòng)求和的過(guò)程是什么？步驟如下：

x+y=a,任務(wù)變?yōu)閍,z,w求和

a+z=b,任務(wù)變?yōu)閎,w求和

b+w=c得出答案

思考一下，【得出答案】這一步為什么就可以得出答案呢？(廢話(huà)？)是因?yàn)椋粋€(gè)數(shù)不用相加就能得出答案.

所以，遞歸的邊界就是只有一個(gè)數(shù).

所以，遞歸邊界有了，那么遞歸公式呢？其實(shí)手動(dòng)計(jì)算過(guò)程中，隱含了遞歸公式：

其中+為求兩個(gè)數(shù)的和，F(xiàn)為求多個(gè)數(shù)的和的遞歸函數(shù).代碼如下：

#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.求數(shù)組元素最大值

手動(dòng)求最大值的過(guò)程是什么，遍歷+比較，過(guò)程如下：

例如，求3,2,6,7,2,4的最大值：先設(shè)置最大值max=-999999，然后將max和數(shù)組元素逐個(gè)(遍歷)比較如果a[i]>max，則更新max的值為a[i]，否則max不變，繼續(xù)向后遍歷，直到遍歷結(jié)束.

max<3，則max=3

max>2，max=3不變

max<6，則max=6

max<7，則max=7

max>2，max=7不變

max>4，max=7不變

遍歷結(jié)束，max=7為最大值.

和求和類(lèi)似，遞歸的公式如下：

其中max為求兩個(gè)數(shù)的較大值函數(shù)，F(xiàn)為求多個(gè)數(shù)的最大值的遞歸函數(shù).代碼如下：

#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; }