定義
遞歸程式調用自身的編程技巧稱為遞歸（ recursion）。
一個過程或函式在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程式就可描述出解題過程所需要的多次重複計算，大大地減少了程式的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。
注意：
(1) 遞歸就是在過程或函式里調用自身；
(2) 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。
其它定義
遞歸遞歸，就是在運行的過程中調用自己。
在數學和計算機科學中，遞歸指由一種（或多種）簡單的基本情況定義的一類對象或方法，並規定其他所有情況都能被還原為其基本情況。
例如，下列為某人祖先的遞歸定義：
某人的雙親是他的祖先（基本情況）。某人祖先的雙親同樣是某人的祖先（遞歸步驟）。斐波納契數列（Fibonacci Sequence），又稱黃金分割數列，指的是這樣一個數列：1、1、2、3、5、8、13、21..... I
斐波納契數列是典型的遞歸案例：
Fib(0) = 0 [基本情況] Fib(1) = 1 [基本情況] 對所有n > 1的整數：Fib(n) = (Fib(n-1) + Fib(n-2)) [遞歸定義] 儘管有許多數學函式均可以遞歸表示，但在實際套用中，遞歸定義的高開銷往往會讓人望而卻步。例如：
階乘（1) = 1 [基本情況] 對所有n > 1的整數：階乘（n) = (n * 階乘（n-1)) [遞歸定義] 一種便於理解的心理模型，是認為遞歸定義對對象的定義是按照“先前定義的”同類對象來定義的。例如：你怎樣才能移動100個箱子？答案：你首先移動一個箱子，並記下它移動到的位置，然後再去解決較小的問題：你怎樣才能移動99個箱子？最終，你的問題將變為怎樣移動一個箱子，而這是你已經知道該怎么做的。
如此的定義在數學中十分常見。例如，集合論對自然數的正式定義是：1是一個自然數，每個自然數都有一個後繼，這一個後繼也是自然數。
德羅斯特效應是遞歸的一種視覺形式。圖中女性手持的物體中有一幅她本人手持同一物體的小圖片，進而小圖片中還有更小的一幅她手持同一物體的圖片，依此類推。
又例如，我們在兩面相對的鏡子之間放一根正在燃燒的蠟燭，我們會從其中一面鏡子裡看到一根蠟燭，蠟燭後面又有一面鏡子，鏡子裡里又有一根蠟燭……這也是遞歸的表現。
算法特點
遞歸遞歸算法解決問題的特點：
(1)遞歸就是在過程或函數裡調用自身。
(2)在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。
(3)遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低。所以一般不提倡用遞歸算法設計程式。
(4)在遞歸調用的過程當中系統為每一層的返回點、局部量等開闢了棧來存儲。遞歸次數過多容易造成棧溢出等。所以一般不提倡用遞歸算法設計程式。
遞歸算法要求
遞歸算法所體現的“重複”一般有三個要求：
一是每次調用在規模上都有所縮小(通常是減半)；
二是相鄰兩次重複之間有緊密的聯繫，前一次要為後一次做準備(通常前一次的輸出就作為後一次的輸入)；
三是在問題的規模極小時必須用直接給出解答而不再進行遞歸調用，因而每次遞歸調用都是有條件的(以規模未達到直接解答的大小為條件)，無條件遞歸調用將會成為死循環而不能正常結束。
遞歸套用
遞歸算法一般用於解決三類問題：(1)數據的定義是按遞歸定義的。（Fibonacci函式）
(2)問題解法按遞歸算法實現。（回溯）
(3)數據的結構形式是按遞歸定義的。（樹的遍歷，圖的搜尋）
遞歸的缺點：
遞歸算法解題相對常用的算法如普通循環等，運行效率較低。因此，應該儘量避免使用遞歸，除非沒有更好的算法或者某種特定情況，遞歸更為適合的時候。在遞歸調用的過程當中系統為每一層的返回點、局部量等開闢了棧來存儲。遞歸次數過多容易造成棧溢出等。
例子：
#include
void move (char getone,char putone)
{
cout < <<"-->"<}
void hanoi(int n,char one,char two,char three)
{
void move (char getone,char putone );
if (n==1)
move (one,three);
else
{
hanoi(n-1,one,three,two);
move (one,three);
hanoi(n-1,two,one,three);
}
}
void main()
{
void hanoi(int n,char one,char two,char three);
int m ;
cout <<"Input the numberof disker:";
cin>>m;
cout<<"the steps to moving "<<<"diskes
:"<
hanoi(m,'A','B','C');
}
如：
procedure a;
begin
a;
end;
這種方式是直接調用.
又如：
procedure b;
begin
c;
end;
procedure c;
begin
b;
end;
這種方式是間接調用.
例1計算n!可用 遞歸公式如下：
1 當 n=0 時
fac(n)={n*fac(n-1) 當n>0時
可編寫程式如下：
program fac2;
var
n:integer;
function fac(n:integer):real;
begin
if n=0 then fac:=1 else fac:=n*fac(n-1)；
end;
begin
write('n=");readln(n);
writeln("fac(',n,')=",fac(n):6:0);
end.
例2 樓梯有n階台階，上樓可以一步上1階，也可以一步上2階，編一程式計算共有多少種不同的走法.
設n階台階的走法數為f(n)
顯然有
1 n=1
f(n)={2 n=2
f(n-1)+f(n-2) n>2
可程式序如下：
program louti;
var n:integer;
function f(x:integer):integer;
begin
if x=1 then f:=1 else
if x=2 then f:=2 else f:=f(x-1)+f(x-2);
end;
begin
write("n=");read(n);
writeln("f(',n,')=",f(n))
end.
2.2 如何設計 遞歸算法
1.確定 遞歸公式
2.確定邊界（終了)條件
練習：
用遞歸的方法完成下列問題
1.求 數組中的最大數
2.1+2+3+...+n
3.求n個整數的積
4.求n個整數的平均值
5.求n個 自然數的最大公約數與最低公倍數
6.有一對雌雄兔，每兩個月就繁殖雌雄各一對兔子.問n個月後共有多少對兔子
7.已知： 數列1,1,2,4,7,13,24,44,...求數列的第 n項.
2.3典型例題
例3 梵塔問題
如圖：已知有三根針分別用1,2,3表示，在一號針中從小放n個盤子，現要求把所有的盤子
從1針全部移到3針，移動規則是：使用2針作為過度針，每次只移動一塊盤子，且每根針上
不能出現大盤壓小盤.找出移動次數最小的方案.
程式如下：
program fanta;
var
n:integer;
procedure move(n,a,b,c:integer);
begin
if n=1 then writeln(a,"--->',c)
else begin
move(n-1,a,c,b);
writeln(a,'--->',c);
move(n-1,b,a,c);
end;
end;
begin
write('Enter n=");
read(n);
move(n,1,2,3);
end.
例4 快速排序
快速排序的思想是：先從數據序列中選一個元素,並將序列中所有比該元素小的元素都放到它的右邊或左邊，再對左右兩邊分別用同樣的方法處之直到每一個待處理的序列的長度為1,處理結束.
程式如下：
program kspv;
var
a:array[0..10000] of longint;
i:integer;
procedure quicksort(l,r:longint);
var i,j,mid:longint;
begin
i:=l;j:=r;mid:=a[(l+r) div 2];
repeat
while a[i]
while a[j]>mid do dec(j);
if i<=j then
begin
a[0]:=a[i];a[i]:=a[j];a[j]:=a[0];
inc(i);dec(j);
until i>j;
if i
if l
end;
begin
write("input data:');
readln(n);
for i:=1 to n do read(a[i]);
writeln;
quicksort(1,n);
write('output data:');
for i:=1 to n do write(a[i],' ');
writeln;
end.
練習：
1.計算ackerman 函式值:
n+1 m=0
ack(m,n)={ ack(m-1,1) m<>0,n=0
ack(m-1,ack(m,n-1)) m<>0,n<>0
求ack(5,4)
