一個(gè)過(guò)程或函數(shù)在其定義或說(shuō)明中又直接或間接調(diào)用自身的一種方法，它通常把一個(gè)大型復(fù)雜的問題轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來(lái)求解燥翅，遞歸策略只需少量的程序就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算柬讨，大大地減少了程序的代碼量罚舱。遞歸的能力在于用有限的語(yǔ)句來(lái)定義對(duì)象的無(wú)限集合继薛。一般來(lái)說(shuō)饲齐，遞歸需要有邊界條件诫隅、遞歸前進(jìn)段和遞歸返回段腐魂。當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)逐纬；當(dāng)邊界條件滿足時(shí)蛔屹，遞歸返回。
遞歸算法一般用于解決三類問題：
（1）數(shù)據(jù)的定義是按遞歸定義的风题。（Fibonacci函數(shù)）
（2）問題解法按遞歸算法實(shí)現(xiàn)判导。（回溯）
（3）數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的。（樹的遍歷沛硅，圖的搜索）
遞歸的執(zhí)行過(guò)程可分為分解和求值兩部分眼刃。首先是逐步把“大問題”分解成形式相同但規(guī)模很小的“小問題”，直至分解到遞歸出口摇肌。一旦遇到遞歸出口擂红，分解過(guò)程結(jié)束，開始求值過(guò)程，所以分解過(guò)程是“量變”過(guò)程昵骤，即原來(lái)的“大問題”在慢慢變小树碱，但尚未解決。遇到遞歸出口后变秦，便發(fā)生了“質(zhì)變”成榜，即原遞歸問題轉(zhuǎn)換成直接可以求值的簡(jiǎn)單問題。遞歸只需要少量的步驟就可描述解題過(guò)程中所需要的多次重復(fù)計(jì)算蹦玫，極大地減少了代碼量赎婚。該算法設(shè)計(jì)的關(guān)鍵在于，找出遞歸方程和邊界條件（遞歸出口）樱溉。遞歸關(guān)系就是使問題向邊界條件轉(zhuǎn)化的過(guò)程挣输，所以遞歸關(guān)系必須能使問題越來(lái)越簡(jiǎn)單，規(guī)模越小福贞。沒有設(shè)定邊界的遞歸是死循環(huán)撩嚼。
遞歸算法設(shè)計(jì)通常需要按照以下3個(gè)步驟：
（1）分析問題，得出遞歸關(guān)系挖帘；
（2）設(shè)置邊界條件完丽，控制遞歸；
（3）設(shè)計(jì)函數(shù)肠套，確定參數(shù)舰涌。
遞歸算法具有以下三個(gè)基本規(guī)則：
（1）基本情形：至少有一種無(wú)需遞歸即可獲得解決的情形，也即前面說(shuō)的邊界條件你稚。
（2）進(jìn)展：任意遞歸調(diào)用必須向基本情形邁進(jìn)瓷耙，即前面所說(shuō)的使得問題規(guī)模變小。
（3）正確性假設(shè)：總是假設(shè)遞歸調(diào)用是有效的刁赖。
遞歸調(diào)用的有效性是可以用數(shù)學(xué)歸納法證明的搁痛，所以當(dāng)我們?cè)谠O(shè)計(jì)遞歸函數(shù)時(shí)，不必設(shè)法跟蹤可能很長(zhǎng)的遞歸調(diào)用途徑（比如Hanoi Tower問題）宇弛。這種任務(wù)可能很麻煩鸡典，易于使設(shè)計(jì)和驗(yàn)證變得更加困難。所以我們一旦決定使用遞歸算法枪芒，則必須假設(shè)遞歸調(diào)用是有效的彻况。
與遞歸相對(duì)應(yīng)的遞推算法是一種用若干步可重復(fù)的簡(jiǎn)單運(yùn)算（規(guī)律）來(lái)描述復(fù)雜問題的方法。
遞推算法以初始（起點(diǎn)）值為基礎(chǔ)舅踪，用相同的運(yùn)算規(guī)律纽甘，逐次重復(fù)運(yùn)算，直至運(yùn)算結(jié)束抽碌。這種從“起點(diǎn)”重復(fù)相同的方法直至到達(dá)一定“邊界”悍赢，猶如單向運(yùn)動(dòng)，用循環(huán)可以實(shí)現(xiàn)。遞推的本質(zhì)是按規(guī)律逐次推出（計(jì)算）先一步的結(jié)果左权。
在算法設(shè)計(jì)時(shí)皮胡，能用遞推實(shí)現(xiàn)的算法一般都可以用遞歸來(lái)實(shí)現(xiàn)。能用遞歸實(shí)現(xiàn)的算法不一定能夠通過(guò)遞推實(shí)現(xiàn)赏迟。就算法的效率而言屡贺，遞推優(yōu)于遞歸
