遞歸題目(共10頁)(1)

1、例題計(jì)算n的階乘#include int factorial(int n) int result; if (n0) /判斷例外 printf(輸入錯(cuò)誤!n); return 0; else if (n=0 | n=1) result = 1; /回推墻 else result = factorial(n-1) * n; /遞推關(guān)系，這個(gè)數(shù)與上一個(gè)數(shù)之間的關(guān)系。 return result;int main() int n = 5; /輸入數(shù)字5，計(jì)算5的階乘 printf(%d的階乘=%d,n,factorial(n); return 0;程序在計(jì)算5的階乘的時(shí)候，先執(zhí)行遞推，當(dāng)n=1或者n=

2、0的時(shí)候返回1，再回推將計(jì)算并返回。由此可以看出遞歸函數(shù)必須有結(jié)束條件。遞歸函數(shù)特點(diǎn)：1.每一級函數(shù)調(diào)用時(shí)都有自己的變量，但是函數(shù)代碼并不會(huì)得到復(fù)制，如計(jì)算5的階乘時(shí)每遞推一次變量都不同；2.每次調(diào)用都會(huì)有一次返回，如計(jì)算5的階乘時(shí)每遞推一次都返回進(jìn)行下一次；3.遞歸函數(shù)中，位于遞歸調(diào)用前的語句和各級被調(diào)用函數(shù)具有相同的執(zhí)行順序；4.遞歸函數(shù)中，位于遞歸調(diào)用后的語句的執(zhí)行順序和各個(gè)被調(diào)用函數(shù)的順序相反；5.遞歸函數(shù)中必須有終止語句。一句話總結(jié)遞歸：自我調(diào)用且有完成狀態(tài)。例題小明為了學(xué)好英語，需要每天記單詞，第一天記1個(gè)，第二天記2個(gè)依次類推，請用代碼完成，算出小明第10天開始的時(shí)候會(huì)了多少個(gè)單

3、詞？ 分析：回推墻是“第一天記1個(gè)”遞推關(guān)系是“第n天記的單詞= 第n-1天記的單詞數(shù)量+n#include /* 定義獲取單詞數(shù)量的函數(shù) */int getWordNumber(n) if(n = 1) return 1; /回推墻 else return getWordNumber(n-1)+n ; /遞推關(guān)系 int main() int num = getWordNumber(10); /獲取會(huì)了的單詞數(shù)量 printf(小明第10天記了:%d個(gè)單詞。n, num); return 0;例題有5個(gè)人坐在一起，問第5個(gè)人多少歲？他說比第4個(gè)人大2歲。問第4個(gè)人歲數(shù)，他說比第3個(gè)人大2歲。

4、問第3個(gè)人，又說比第2人大兩歲。問第2個(gè)人，說比第1個(gè)人大兩歲。最后 問第1個(gè)人，他說是10歲。請問第5個(gè)人多大？程序分析：利用遞歸的方法，遞歸分為回推和遞推兩個(gè)階段。要想知道第5個(gè)人歲數(shù)，需知道第4人的歲數(shù)，依次類推，推到第1人（10歲），再往回推。#include /* 請使用遞歸函數(shù)完成本題* 小編已將正確代碼放在左側(cè)任務(wù)的“不知道怎么辦”里* 小編希望各位童鞋獨(dú)立完成哦*/定義一個(gè)函數(shù)，傳送人員序號(hào)進(jìn)去，返回該序號(hào)員工的年齡。int getAge(numPeople) /定義返回的年齡 int age; /如果是第1個(gè)人的時(shí)候，年齡為10歲 if(numPeople=1) age=10

5、; /這是回推墻，也就是結(jié)束遞歸的條件。 else /還沒接觸到回推墻，就自我調(diào)用，謂之遞歸。 age = getAge(numPeople-1)+2; /年齡等于上一個(gè)人的年齡加2 return age;int main() printf(第5個(gè)人的年齡是%d歲, getAge(5);return 0;例題猴子第一天摘下N個(gè)桃子，當(dāng)時(shí)就吃了一半，還不過癮，就又多吃了一個(gè)。第二天又將剩下的桃子吃掉一半，又多吃了一個(gè)。以后每天都吃前一天剩下的一半零一個(gè)。到第10天在想吃的時(shí)候就剩一個(gè)桃子了,問第一天共摘下來多少個(gè)桃子？并反向打印每天所剩桃子數(shù)。#include /定義一個(gè)函數(shù)，輸入第n天，返回該

6、天剩下的桃子數(shù)int getPeachNumber(n) int num; /定義所剩桃子數(shù) if(n=10) num=1; /遞歸結(jié)束條件，即回推墻 return num; else num = (getPeachNumber(n+1) + 1) * 2; /遞推關(guān)系 printf(第%d天所剩桃子%d個(gè)n, n, num); /天數(shù)，所剩桃子個(gè)數(shù) return num;int main() int num = getPeachNumber(1); printf(猴子第一天摘了:%d個(gè)桃子。n, num); return 0;遞歸（recursion）：程序調(diào)用自身的編程技巧。 遞歸滿足2個(gè)

7、條件： 1）有反復(fù)執(zhí)行的過程（調(diào)用自身） 2）有跳出反復(fù)執(zhí)行過程的條件（遞歸出口）遞歸例子：（1）階乘 n! = n * (n-1) * (n-2) * .* 1(n0)/階乘int recursive(int i)int sum = 0;if (0 = i)return (1);elsesum = i * recursive(i-1);return sum;（2）河內(nèi)塔問題/河內(nèi)塔void hanoi(int n,int p1,int p2,int p3)if(1=n)cout盤子從p1移到p3endl;elsehanoi(n-1,p1,p3,p2);cout盤子從p1移到p3endl;ha

8、noi(n-1,p2,p1,p3);（3）全排列 從n個(gè)不同元素中任取m（mn）個(gè)元素，按照一定的順序排列起來，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列。當(dāng)m=n時(shí)所有的排列情況叫全排列。 如1,2,3三個(gè)元素的全排列為： 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1/全排列inline void Swap(int &a,int &b)int temp=a;a=b;b=temp;void Perm(int list,int k,int m)if (k = m-1) for(int i=0;im;i+)printf(%d,listi);printf(n);elsefo

9、r(int i=k;i 1)return Fib(n-1) + Fib(n-2);（4）判定一系列字符串中是否有相同的內(nèi)容public class T public static void main(String args) String a = a1,a2,a3,b3,c,b,33,33; boolean b = new T().fun(0, a); System.out.println(b); public boolean fun(int n,String a) boolean b = false; if(n = a.length) b = true; else for(int i = n

10、; i =2;這個(gè)明顯地給出了遞歸邊界n=0或1的時(shí)候F(n)的值，和遞歸邏輯F(n)=F(n-1)+F(n-2)，即遞推公式.所以這個(gè)遞歸函數(shù)不難書寫int F(int n)/函數(shù)返回一個(gè)數(shù)對應(yīng)的Fibonacci數(shù)2.階乘 階乘的遞歸公式為：3.數(shù)組求和給一個(gè)數(shù)組a:a0,a1,.,an-1如何用遞歸的方式求和？仍然是兩個(gè)問題：遞歸邊界和遞歸公式.遞歸邊界是什么？一時(shí)不容易想到，但是我們想到了求和，多個(gè)數(shù)的求和過程是什么，x,y,z,w手動(dòng)求和的過程是什么？步驟如下：x+y=a,任務(wù)變?yōu)閍,z,w求和a+z=b,任務(wù)變?yōu)閎,w求和b+w=c得出答案思考一下，【得出答案】這一步為什么就可以得

11、出答案呢？(廢話？)是因?yàn)椋粋€(gè)數(shù)不用相加就能得出答案.所以，遞歸的邊界就是只有一個(gè)數(shù).所以，遞歸邊界有了，那么遞歸公式呢？其實(shí)手動(dòng)計(jì)算過程中，隱含了遞歸公式：其中+為求兩個(gè)數(shù)的和，F(xiàn)為求多個(gè)數(shù)的和的遞歸函數(shù).代碼如下：#includeusing namespace std; int F(int a,int start,int end)if(start=end)/遞歸邊界return astart; return astart + F(a,start+1,end);/遞歸公式 int main()int a = 1,2,3,4,5;int s=0,e=4;cout F(a,s,e) max，則更新max的值為ai，否則max不變，繼續(xù)向后遍歷，直到遍歷結(jié)束.max2，max=3不變max6，則max=6max2，max=7不變max4，max=7不變遍歷結(jié)束，max=7為最大值.和求和類似，遞歸的公式如下：其中max為求兩個(gè)數(shù)的較大值函數(shù)，F(xiàn)為求多個(gè)數(shù)的最大值的遞歸函數(shù).代碼如下：#includeusing namespace std;#define max(a,b) (ab?a:b)int F(int a,int s,int e)if(s=e)return as;else if(s+1 = e)/遞歸邊界return m