1. 算法簡(jiǎn)介

遞推和遞歸雖然叫法不同，但它們的基本思想是一致的，在很多程序中，這兩種算法可以通用，不同的是遞推法效率更高，遞歸法更方便閱讀。

（1）遞推法

遞推法是一種重要的數(shù)學(xué)方法，同時(shí)也是計(jì)算機(jī)進(jìn)行數(shù)值計(jì)算的個(gè)重要算法。
遞推法的核心是找到計(jì)算前后過(guò)程之間的數(shù)量關(guān)系，即遞推式。遞推式往往根據(jù)已知條件和所求問(wèn)題之間存在的某種相互聯(lián)系推導(dǎo)得出。遞推計(jì)算時(shí)，需要將復(fù)雜運(yùn)算轉(zhuǎn)換為若干步重復(fù)的簡(jiǎn)單運(yùn)算，這樣可以發(fā)揮計(jì)算機(jī)擅于重復(fù)處理數(shù)據(jù)的特點(diǎn)。遞推法避開(kāi)了求通項(xiàng)公式的麻煩，把一個(gè)復(fù)雜問(wèn)題的求解分解成了連續(xù)的若干歩簡(jiǎn)單運(yùn)算，可以將遞推法看成一種特殊的迭代算法。
[案例解析]鋪方格
有2×n個(gè)長(zhǎng)方形的方格，用一個(gè)1×2的骨牌鋪滿方格。例如當(dāng)0=3時(shí)為2×3方格，骨牌的鋪放方案有3種，

?骨牌鋪設(shè)方案（1）
編寫(xiě)一個(gè)程序，試對(duì)給出的任意一個(gè)n(n>0)輸出鋪法總數(shù)。針對(duì)這個(gè)問(wèn)題，要想直接獲得問(wèn)題的解答是相當(dāng)困難的。可以用遞推法，從簡(jiǎn)單到復(fù)雜逐步歸納出問(wèn)題解的一般規(guī)律。分析過(guò)程如下。
當(dāng)n=1時(shí)，只能有一種鋪法 ，如圖4-2(a)所示，鋪法總數(shù)為X1=1。
當(dāng)n=2時(shí)，骨牌可以并列豎排，也可以并列橫排，再無(wú)其他排列方法，如圖2(b)所示，鋪法總數(shù)為X2?=2。
當(dāng)n=3時(shí),骨牌可以全部豎排，也可以認(rèn)為在方格中已經(jīng)有一個(gè)豎排骨牌、需要在方格中排列兩個(gè)橫排骨牌(無(wú)重復(fù)方法)，若已經(jīng)在方格中排列兩個(gè)橫排骨牌，則必須在方格中排列一個(gè)豎排骨牌，如圖2(c)所示，再無(wú)其他排列方法,鋪法總數(shù)為X3= 3。

?

骨牌鋪放方案(2)
由此可以看出，當(dāng)n=3時(shí)，排列骨牌的方法數(shù)是n=1和n=2時(shí)排列方法數(shù)之和。
推出一般規(guī)律，對(duì)一般的n，要求Xn?？梢赃@樣考慮：若第一個(gè)骨牌是豎排列，則剩下n-1個(gè)骨牌需要排列，這時(shí)排列方法數(shù)為Xn-1，若第一個(gè)骨牌是橫排列，則整個(gè)方格至少有2個(gè)骨牌是橫排列(1×2骨牌)，因此剩下n-2個(gè)骨牌需要排列，這時(shí)排列方法數(shù)為Xn-2從第一種骨牌排列方法考慮，只有這兩種可能,所以有：

Xn=Xn-1+Xn-2(n> 2)

X1=1

X2=2

Xn=Xn-1+ Xn-2就是問(wèn)題求解的遞推公式

任意n都可以從中獲得解答。
例如n=5，

X3=X2+X1=3

X4=X3+X2=5

X5=X4+X3=8

利用程序表示為：

cin>>n;  
a[1]=1;a[2]=2;  
for(i=3;i<=n; i++)
a[i]=a[i-1]+a[i-2];
cout<<a[n]<<"";

（2）遞歸法

在計(jì)算機(jī)科學(xué)中，如果某個(gè)函數(shù)的實(shí)現(xiàn)中出現(xiàn)了對(duì)函數(shù)自身的調(diào)用語(yǔ)句，則稱該函數(shù)為遞歸函數(shù)。
遞推法可以用遞歸函數(shù)實(shí)現(xiàn)。一般來(lái)說(shuō)，循環(huán)遞推法比遞歸函數(shù)的速度更快，但遞歸函數(shù)的可讀性更強(qiáng)。
例如，上述平鋪方格問(wèn)題改寫(xiě)成遞歸函數(shù)的形式如下。

int pu(int n)
{
if(n==1) return 1;
if(n==2) return 2;
return pu(n-1) +pu(n-2);
}

遞歸函數(shù)在它的函數(shù)體內(nèi)直接或者間接地調(diào)用自身，每調(diào)用一次，就進(jìn)入新的一層。遞歸函數(shù)必須有結(jié)束遞歸的條件。函數(shù)會(huì)一直遞推 ，直到遇到結(jié)束 條件返回，遞歸函數(shù)調(diào)用的一般過(guò)程如圖3所示,這里以n=6為例。

?遞歸函數(shù)的調(diào)用過(guò)程

2. ?取數(shù)位（2017年試題E）

【問(wèn)題描述】
求一個(gè)整數(shù)的第k位數(shù)字有很多種方法，以下下方法就是其中一種。
//求x用十進(jìn)制表示時(shí)的數(shù)位長(zhǎng)度

int len(int x){
if(x<10) return 1;
return len(x/10)+1;
}
//取x的第k位數(shù)字
int f(int x, int k) {
if(len(x)-k==0) returnx%10;
return (     )  ；//填空
}
int main()
int x= 23574;
printf("&d\n", f(x,3));
return 0;
}

對(duì)于題目中的測(cè)試數(shù)據(jù)，應(yīng)該打印5。
請(qǐng)仔細(xì)分析源碼，并補(bǔ)充畫(huà)線部分缺少的代碼。
注意：只提交缺失的代碼，不要填寫(xiě)任何已有內(nèi)容或說(shuō)明性文字。

答案——取數(shù)位

  //求 x 用十進(jìn)制表示時(shí)的數(shù)位長(zhǎng)度int len(int x){if(x<10) return 1;return len(x/10)+1;}//取 x 的第 k 位數(shù)字int f(int x, int k) {if(len(x)-k==0) return x%10;return f(x/10,k) ；//填空}int main()int x= 23574;printf("&d\n", f(x,3));return 0;}