C語言遞歸操作用法總結(jié)
本文實例總結(jié)了C語言遞歸操作用法。分享給大家供大家參考,具體如下:
用歸納法來理解遞歸
步進(jìn)表達(dá)式:問題蛻變成子問題的表達(dá)式
結(jié)束條件:什么時候可以不再是用步進(jìn)表達(dá)式
直接求解表達(dá)式:在結(jié)束條件下能夠直接計算返回值的表達(dá)式
邏輯歸納項:適用于一切非適用于結(jié)束條件的子問題的處理,當(dāng)然上面的步進(jìn)表達(dá)式其實就是包含在這里面了。
遞歸算法的一般形式:
void func( mode) { if(endCondition) { constExpression //基本項 } else { accumrateExpreesion //歸納項 mode=expression //步進(jìn)表達(dá)式 func(mode) //調(diào)用本身,遞歸 } }
最典型的就是N!算法,這個最具有說服力。理解了遞歸的思想以及使用場景,基本就能自己設(shè)計了,當(dāng)然要想和其他算法結(jié)合起來使用,還需要不斷實踐與總結(jié)了。
#include "stdio.h" #include "math.h" int main(void) { int n, rs; printf("請輸入需要計算階乘的數(shù)n:"); scanf("%d",&n); rs = factorial(n); printf("%d ", rs); } // 遞歸計算過程 int factorial(n){ if(n == 1) { return 1; } return n * factorial(n-1); }
遞歸的基本思想是把規(guī)模大的問題轉(zhuǎn)化為規(guī)模小的相似的子問題來解決。在函數(shù)實現(xiàn)時,因為解決大問題的方法和解決小問題的方法往往是同一個方法,所以就產(chǎn)生了函數(shù)調(diào)用它自身的情況。另外這個解決問題的函數(shù)必須有明顯的結(jié)束條件,這樣就不會產(chǎn)生無限遞歸的情況了。
能用遞歸來解決的問題必須滿足兩個條件:
① 可以通過遞歸調(diào)用來縮小問題規(guī)模,且新問題與原問題有著相同的形式。
② 存在一種簡單情境,可以使遞歸在簡單情境下退出。
如果一個問題不滿足以上兩個條件,那么它就不能用遞歸來解決。
為了方便理解,還是拿斐波那契數(shù)列來說下:求斐波那契數(shù)列的第N項的值。
這是一個經(jīng)典的問題,說到遞歸一定要提到這個問題。斐波那契數(shù)列這樣定義:f(0) = 0, f(1) = 1, 對n > 1, f(n) = f(n-1) + f(n-2)
這是一個明顯的可以用遞歸解決的問題。讓我們來看看它是如何滿足遞歸的兩個條件的:
1.對于一個n>2, 求f(n)只需求出f(n-1)和f(n-2),也就是說規(guī)模為n的問題,轉(zhuǎn)化成了規(guī)模更小的問題;
2. 對于n=0和n=1,存在著簡單情境:f(0) = 0, f(1) = 1。
因此,我們可以很容易的寫出計算費(fèi)波納契數(shù)列的第n項的遞歸程序:
int fib(n){ if(n == 0) return 0; else if(n == 1) return 1; else return f(n-1) + f(n-2); }
在編寫遞歸調(diào)用的函數(shù)的時候,一定要把對簡單情境的判斷寫在最前面,以保證函數(shù)調(diào)用在檢查到簡單情境的時候能夠及時地中止遞歸,否則,你的函數(shù)可能會永不停息的在那里遞歸調(diào)用了。
判斷一個字符串是否是回文:
function huiwen($str) { if(strlen($str)==1 || strlen($str)==0){ return 1; }else{ if($str[0]==$str[strlen($str)-1]){ $str = substr($str,1,-1);; echo $str."<br/>"; return huiwen($str); }else{ return 0; } } }
希望本文所述對大家C語言程序設(shè)計有所幫助。
相關(guān)文章
關(guān)于c語言逗號表達(dá)式的運(yùn)算規(guī)則知識點(diǎn)
在本篇文章里小編給大家整理的是關(guān)于c語言逗號表達(dá)式的運(yùn)算規(guī)則知識點(diǎn),需要的朋友們可以學(xué)習(xí)參考下。2020-03-03C++執(zhí)行shell命令的多種實現(xiàn)方法
在linux系統(tǒng)下,用C++程序執(zhí)行shell命令有多種方式,主要介紹了3中方法,具有一定的參考價值,感興趣的可以了解一下2021-11-11

C++語言基礎(chǔ) this和static關(guān)鍵字