遞歸算法實(shí)例及程序?qū)崿F(xiàn)

遞歸算法實(shí)例及程序?qū)崿F(xiàn)從前有座山，山里有座廟，廟里有個(gè)老和尚，給小和尚講故事，故事是什么呢？從前有座山，山里有座廟，廟里有個(gè)老和尚，給小和尚講故事，故事是什么呢？從前有座山，山里有座廟，廟里有個(gè)老和尚，給小和尚講故事，故事是什么呢？老和尚的故事…數(shù)果子問題233142？數(shù)果子問題遞歸

將要處理的問題劃分為一個(gè)或多個(gè)子問題，而處理子問題的方法與處理原問題的方法是一樣的，這樣的處理方法稱為遞歸。案例一、到底幾歲了？我比左邊的2倍小2歲我比左邊的2倍小2歲我比左邊的2倍小2歲我比左邊的2倍小2歲我比左邊的2倍小2歲我比左邊的2倍小2歲我3歲案例一、到底幾歲了？算法規(guī)則：1、第1個(gè)人的年齡=3\2、第N個(gè)人的年齡=第N-1人的年齡*2-2求第N個(gè)人的年齡：if是第1個(gè)人then年齡=3 else年齡=前一人年齡*2-2 endif案例一、到底幾歲了？VB代碼：FunctionAge(nAsInteger)AsIntegerifn=1thenage=3elseage=age(n-1)*2-2endifEndFunction求第N個(gè)人的年齡if是第一個(gè)人then

年齡=3else

年齡=前一人年齡*2-2endif案例二、斐波那契數(shù)列問題斐波納契數(shù)列，又稱黃金分割數(shù)列，指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、34、65……這個(gè)數(shù)列從第三項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和。求：數(shù)列中的第N項(xiàng)是幾？算法規(guī)則：1、最初兩項(xiàng)值為12、第N項(xiàng)的值是它之前兩項(xiàng)之和求第N個(gè)斐波納切數(shù)if是最初兩項(xiàng)then斐波納切數(shù)=1 else斐波納切數(shù)=前兩個(gè)斐波納切數(shù)之endif案例二、斐波那契數(shù)列問題求第N個(gè)斐波納切數(shù)if是最初兩項(xiàng)then斐波納切數(shù)=1 else斐波納切數(shù)=前兩個(gè)斐波納切數(shù)之和endifFunctionFib(nasInteger)asIntegerIfthenFib=ElseFib=EndifEndFunctionn<3Fib(n-2)+Fib(n-1)11、1、2、3、5、8、13、21、34、65……案例三、求最大公約數(shù)

早在公元前300年左右，歐幾里得就在他的著作《幾何原本》中給出了高效的解法——輾轉(zhuǎn)相除法。輾轉(zhuǎn)相除法的方法是用較大的數(shù)X除以較小的數(shù)Y，得到余數(shù)Z；

如果余數(shù)為0，則較小數(shù)Y就是兩者的最大公約數(shù)。例如：27和9的最大公約數(shù)就是9。如果余數(shù)不為0，則較小數(shù)Y與余數(shù)Z的最大公約數(shù)就是X與Y的的最大公約數(shù)。例如：33和9的最大公約數(shù)就是9與6的最大公約數(shù)。案例三、求最大公約數(shù)求X與Y的公約數(shù)：Z是X除Y得到的余數(shù)IfZ為0then

公約數(shù)=Else

公約數(shù)=的公約數(shù)EndifFunctionGYS(xasInteger,yasInteger)asIntegerDimzasIntegerz=IfZ=0thenGYS=ElseGYS=EndifEndFunctionXmodYYGYS(Y,Z)Y和ZY遞歸算法小結(jié)在程序中，遞歸算法表現(xiàn)為函數(shù)在運(yùn)行過程中調(diào)用了自己。每一次遞歸調(diào)用，在處理問題的規(guī)模上都有所縮小，在問題的規(guī)模極小時(shí)，必須能給出直接的解答。求年齡：FunctionAge(nAsInteger)AsIntegerifn=1thenage=3elseage=age(n-1)*2-2endifEndFunction求斐波那契數(shù)：FunctionFib(nasInteger)asIntegerIfn<3thenFib=1ElseFib=Fib(n-2)+Fib(n-1)EndifEndFunction從前有座山，山里有座廟，廟里有個(gè)老和尚，給小和尚講故事，故事是什么呢？從前有座山，山里有座廟，廟里有個(gè)老和尚，給小和尚講故事，故事是什么呢？從前有座山，山里有座廟，廟里有個(gè)老和尚，給小和尚講故事，故事是什么呢？再看老和尚的故事…這個(gè)過程算不算是遞歸？怎么改才能算是遞歸？拓展練習(xí):求n!n!=1×2×3×4×……×nn!=(n-1)!×n1!=1拓展練習(xí):惡魔與農(nóng)夫有一位農(nóng)夫不滿于自己的貧困。一天,他正在抱怨上天的不公平,一個(gè)惡魔出現(xiàn)在他的眼前，他對(duì)農(nóng)夫說:“