C語言知識點丨遞歸函數(shù)
發(fā)布時間：2023-11-17 16:21:48
1.函數(shù)遞歸的定義
一個函數(shù)在它的函數(shù)體內(nèi)調(diào)用它自身稱為遞歸調(diào)用，這種函數(shù)稱為遞歸函數(shù)。遞歸做為一種算法在程序設計語言中廣泛應用。它通常把一個大型復雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解。
2.函數(shù)遞歸的優(yōu)缺點
優(yōu)點：
函數(shù)遞歸只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。
缺點：
①如果函數(shù)遞歸使用不恰當，會導致棧溢出，因為每一次函數(shù)調(diào)用都會在棧區(qū)上申請內(nèi)存空間。
②每一次函數(shù)遞歸（函數(shù)調(diào)用）都會在函數(shù)棧幀上開辟一塊空間，所謂的壓棧。這樣會大大降低我們代碼的執(zhí)行效率。
3.函數(shù)遞歸的兩個必要條件
存在限制條件，當滿足這個限制條件的時候，遞歸便不再繼續(xù)。
每次遞歸調(diào)用之后越來越接近這個限制條件。
1.函數(shù)遞歸之死循環(huán)
在了解了函數(shù)遞歸的基礎概念后，來看看這段代碼，它的運行結(jié)果是什么呢？
程序最終會崩潰。因為每一次函數(shù)調(diào)用都會在棧上開辟一塊空間，這種死循環(huán)的代碼會一直開辟空間，直至棧溢出。
2.輸入輸出1234
【題目描述】
接受一個整型值（無符號），按照順序打印它的每一位。例如：
輸入：1234，輸出1234。
【解題思路】
這種輸入輸出數(shù)字的題，我們一定要想到取模和取余的方法，并且要有限制條件，每次函數(shù)遞歸后，都會越來越接近這個值。
所以先函數(shù)遞推1234%10=4,123%10=3,12%10=2,1%10=1，給定限制條件n>9,直到n=1，打印出最后值“1”，最后函數(shù)回歸打印出1234。
設n為1234 print(1234/10) + 1234%10 (=4) print(123/10) + 123%10（=3） print(12/10) + 12%10（=2） 當n最后為1時，不滿足我們給定的限制條件n>9時，即打印1%10（=1）
【代碼如下】
1.求n的階乘
【題目描述】
用遞歸的方法求n的階乘（不考慮溢出）。例如：
輸入：4，輸出24。
【解題思路】
n的階乘為1*2*3*4*…*(n-1)*n，我們可以先用遞推的思想，先算出n*(n-1)的值，再用n*(n-1)的值乘以(n-2),這樣依次乘下去，以n=1為限制條件，返回1。然后再用回歸思想，返回回去，及可得到n的階乘。
JC(n) n * JC(n-1) n * JC(n-1) * JC(n-2) n * JC(n-1) * JC(n-2) * JC(n-3) … n * JC(n-1) * JC(n-2) * JC(n-3)…JC(1) 當滿足我們的限制條件n=1時，返回1，然后回歸
【代碼如下】
2.strlen函數(shù)的模擬實現(xiàn)
【題目描述】
用遞歸的方法模擬實現(xiàn)strlen函數(shù)。例如：
輸入：abc，輸出3。
【解題思路】
strlen遇到’\0’才會停止，所以我們以’\0’為限制條件，我們每調(diào)用一次my_strlen函數(shù)，次數(shù)就加一，直到遇到’\0’停止。
my_strlen(abc)--------------這里是指針在移動 1+my_strlen(bc) 1+my_strlen(b) 1+my_strlen(‘\0’) 當滿足我們的**限制條件’\0’**時，返回0，然后回歸。
【代碼如下】
3.字符串逆序
- 上一篇：超詳解答：C語言|字符數(shù)組和字符串
- 下一篇：什么是編程語言
