c語言中什麼是遞迴？經典遞迴函數範例分享

c語言中什麼是遞迴？以下這篇文章就來帶大家透過經典遞歸函數範例來了解一下c語言中的遞歸，希望對大家有幫助！

遞歸是一個過程或函數在其定義或說明中有直接或間接呼叫自身的一種方法；遞歸函數就是直接或間接呼叫自身的函數，也就是自身呼叫自己的過程。

剛接觸遞歸的同學，可能難以理解遞歸，難以理解的點可能很多，例如：

• 函數為什麼可以在自己的內部又調用自己呢?

• 既然可以自己呼叫自己，那麼遞迴運行過程中一定回有很多層相互嵌套，到底什麼時候不再嵌套呢？

• 遞迴運行過程中，相互嵌套的多層之間會有參數傳遞，多層之間是否會相互影響？

遞迴兩個元素

• 遞迴邊界

• 遞迴的邏輯－遞迴」公式"

遞歸的過程一定有參數的變化，並且參數的變化，和遞歸邊界有關係.

在難度較大的題目中，這兩者均不容易直接得到.

遞歸的種種問題，也許理解的同學可能可以用一句話解釋清楚，但是不理解的同學再怎麼說也沒辦法理解.

下面通過幾個簡單的例子【體會】一下遞歸，先從【感性】的角度理解遞歸.

#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.階乘的遞迴公式：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.數組求和

給一個數組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為求多個數的和的遞歸函數.程式碼如下：

#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不改變，繼續向後遍歷，直到遍歷結束.

maxd2dfc039904630c353be64852ca0ea752，max=3不變

max024eeb01fcb106f15049c0a05c6bd60e2，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;
}

之所以，說上面的幾個例子是【簡單例子】，是因為上述所有的遞歸都屬於【單向遞歸】 .單向遞歸，遞歸的路徑就是一個方向，所以思路相對比較容易想到.

較難的遞歸問題，一般都不是單向遞歸，而是需要使用【回溯】的方法，遞歸的方法不太容易想到.

以上是c語言中什麼是遞迴？經典遞迴函數範例分享的詳細內容。更多資訊請關注PHP中文網其他相關文章！