基礎知識
對於某些與自然數有關的問題，我們有時可以用遞推法解決，扎謂用遞推法解題，就是根據題目的特點，構造出遞推關係解題的一種方法，解決問題的關鍵在於構造遞推關係。遞推關係一般可以用歸納、猜想等途徑獲得。
利用遞推法解題的一般步驟為：(1)確定初始值；(2)建立遞推關係；(3)利用遞推關係求通項。
遞推方法是人們從開始認識數量關係時就很自然地產生的一種推理思想.例如自然數中最小的數是1，比1大1的數是2，接下來比2大1的數是3，…由此得到了自然數數列：1，2，3，4，5，….
在這裡實際上就有了乙個遞推公式，假設第n個數為an，則an+1=an+1; 即由自然數中第n個數加上1，就是第n+1個數。由此可得 an＋2=an＋1＋1，這樣就可以得到自然數數列中任何乙個數.
再看乙個例子：
平面上5條直線最多能把圓的內部分成幾部分？平面上100條直線最多能把圓的內部分成幾部分？
解：假設用ak表示k條直線最多能把圓的內部分成的部分數.這裡k＝0，1，2，….
a0＝1
a1=a0+1＝2
a2=a1＋2=4
a3=a2＋3=7
a4=a3+4＝11
…歸納出遞推公式an＋1＝an+n. （1）
即畫第n＋1條直線時，最多增加n部分.原因是這樣的：第一條直線最多把圓分成兩部分，故a1＝2.
當畫第二條直線時要想把圓內部分割的部分盡可能多，就應和第一條直線在圓內相交，交點把第二條直線在圓內部分分成兩條線段，而每條線段又把原來的乙個區域劃分成兩個區域，因而增加的區域數是2，正好等於第二條直線的序號.同理，當畫第三條直線時，要想把圓內部分割的部分數盡可能多，它就應和前兩條直線在圓內各有乙個交點.兩個交點把第三條線在圓內部分成三條線段.
而每條線段又把原來乙個區域劃分成兩個區域.因而增加的區域部分數是3，正好等於第三條直線的序號，….這個道理適用於任意多條直線的情形.
所以遞推公式（1）是正確的.這樣就易求得5條直線最多把圓內分成：
a5=a4+5＝11=5＝16（部分）。
要想求出100條直線最多能把圓內分成多少區域，就去求通項公式。
一般來說，如果乙個與自然數有關的數列中的任一項an可以由它前面的k（≤n-1）項經過運算或其他方法表示出來，我們就稱相鄰項之間有遞迴關係，並稱這個數列為遞迴數列.如果這種推算方法能用公式表示出來，就稱這種公式為遞推公式或遞推關係式.通過尋求遞迴關係來解決問題的方法就稱為遞推方法.
許多與自然數有關的數學問題都常常具有遞推關係，可以用遞推公式來表達它的數量關係.如何尋求這個遞推公式是解決這類問題的關鍵之一，常用的方法是「退」到問題最簡單情況開始觀察.逐步歸納並猜想一般的速推公式.
在小學生階段，我們僅要求學生能撥開問題的一些表面現象由簡到繁地歸納出問題的遞推公式就行了，不要求嚴格證明.當然能證明更好.所謂證明，就是要嚴格推出你建立的關係式適合所有的n，有時，僅僅在前面幾項成立的關係式，不一定當n較大時也成立。
1、 「河內塔問題」
傳說在印度的佛教聖地貝拿勒斯聖廟裡安放著個乙個黃銅板，板上插著三根寶石針，在第一根寶石針上，從下到上穿著由大到小的64片中心有孔的金片.每天都有乙個值班僧侶按下面規則移動金片：把金片從第一根寶石針移到其餘的某根寶石針上.
要求一次只能移動一片，而且小片永遠要放在大片的上面.當時傳說當64片金片都按上面的規則從第一根寶石針移到另一根寶石針上時，世界將在一聲霹靂中毀滅.所以有人戲稱這個問題叫「世界末日」問題（也稱為「hanoi塔」問題），當然，移金片和世界毀滅並無聯絡，這只是乙個傳說而已，但說明這是乙個需要移動很多很多次才能辦到的事情.
解這個問題的方法在演算法分析中也常用到.究竟按上述規則移動完成64片金片需要移動多少次呢？
將此問題一般化為：
設有個銀圈，大小不同，從大到小排列在三根金棒中的一根。這些銀圈要搬到另一根金棒上，每次搬乙個。第三根金棒作為銀圈暫時擺放用。
在搬動過程中，仍要保持大圈在下，小圈在上，問要搬動多少次，才能將所有銀圈從一根棒搬到另一根，且搬完後銀圈相對位置不變？
思路：尋找與前面各項之間的關係，由題設條件列出等式。
解：令用表所求的搬動次數，把第一棒個銀圈的個搬到第三棒，再將最大乙個銀圈搬到第二棒，然後又將第三棒上的個圈搬到第二棒上，如此繼續，可完成這次搬動任務。
因為搬個銀圈從一棒到另一棒需次，故可得遞推式。
下面對遞推式的求解。
最後，可得。
典例分析
例1．用100元人民幣購買物品，規定每天只能用以下三種方式之一購買物品：
(1)買甲物品1元；(2)買乙物品2元；(3)買丙物品2元
而且規定不允許不買物品。試問有多少種方式花完這100元錢？
例2．有一種用硬幣下棋的遊戲，棋盤上標有第0站，第1站，第2站，……，第100站。一枚棋子開始在第0站，棋手每擲一次硬幣，棋子跳動一次：若擲出的是正面，棋子向前跳兩站，若擲出的是反面，則棋子向前跳一站，直到棋子恰好跳到第99站(勝利大本營)或第100站(失敗大本營)時，遊戲結束。
如果硬幣出現正反面的概率都是，分別求棋子跳到勝利大本營與失敗大本營的概率。
例3．現有四個人做傳球遊戲，要求接球後馬上傳給別人。由甲先傳球，並作為第1次傳球，求經過10次傳球仍回到發球人甲手中的傳球方式的種數。
例4．(bernoulli-euler裝錯信問題)某人寫了n封信，並在每個信封上寫下了對應的位址和收信人的姓名。問：將所有的信都錯信封的情況共有多少種？
例5．現將n邊形的邊依次記為，每條邊都塗上紅、黃、綠三種顏色中的一種，要使相鄰兩邊的顏色互不相同，有多少種不同的塗色方法？
例6．(第五屆西部競賽題)已知可以表示成為變元的二次多項式，求這個多項式的係數之和。
例7．已知函式，數列是公差為等差數列，數列為公比為的等比數列，且，；，。設數列對於任意的正整數n都有成立，求的值。
例8．已知一列非零向量滿足：， ()
(1)證明：是等比數列；
(2)求向量與向量的夾角；
(3)設向量，把，，……，中所有與共線的向量取出按原來的順序排成一列，組成一組新數列，記為：，，……，，求數列{}的通項公式；若令
=++…+，為座標原點，求點列的座標。
06高中物理競賽解題方法 遞推法
六 遞推法 方法簡介 遞推法是解決物體與物體發生多次作用後的情況。即當問題中涉及相互聯絡的物體較多並且有規律時，應根據題目特點應用數學思想將所研究的問題歸類，然後求出通式。具體方法是先分析某一次作用的情況，得出結論。再根據多次作用的重複性和它們的共同點，把結論推廣，然後結合數學知識求解。用遞推法解題...
物理奧賽解題方法第6節遞推法
六 遞推法 方法簡介 遞推法是解決物體與物體發生多次作用後的情況.即當問題中涉及相互聯絡的物體較多並且有規律時，應根據題目特點應用數學思想將所研究的問題歸類，然後求出通式.具體方法是先分析某一次作用的情況，得出結論.再根據多次作用的重複性和它們的共同點，把結論推廣，然後結合數學知識求解.用遞推法解題...
高中奧林匹克物理競賽解題方法遞推法
方法簡介 遞推法是解決物體與物體發生多次作用後的情況。即當問題中涉及相互聯絡的物體較多並且有規律時，應根據題目特點應用數學思想將所研究的問題歸類，然後求出通式。具體方法是先分析某一次作用的情況，得出結論。再根據多次作用的重複性和它們的共同點，把結論推廣，然後結合數學知識求解。用遞推法解題的關鍵是匯出...