程式調用自身的程式設計技巧稱為遞歸（ recursion）。遞歸做為一種算法在程式設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸政策隻需少量的程式就可描述出解題過程所需要的多次重複計算，大大地減少了程式的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸傳回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸傳回。
遞歸，就是在運作的過程中調用自己。
構成遞歸需具備的條件：
函數嵌套調用過程示例
1. 子問題須與原始問題為同樣的事，且更為簡單；
2. 不能無限制地調用本身，須有個出口，化簡為非遞歸狀況處理。
在數學和計算機科學中，遞歸指由一種（或多種）簡單的基本情況定義的一類對象或方法，并規定其他所有情況都能被還原為其基本情況。
例如，下列為某人祖先的遞歸定義：
某人的雙親是他的祖先（基本情況）。某人祖先的雙親同樣是某人的祖先（遞歸步驟）。斐波納契數列（fibonacci sequence），又稱黃金分割數列，指的是這樣一個數列：1、1、2、3、5、8、13、21..... i[1]
斐波納契數列是典型的遞歸案例：
遞歸關系就是實體自己和自己建立關系。
fib(0) = 1 [基本情況] 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)資料的定義是按遞歸定義的。（fibonacci函數）
(2)問題解法按遞歸算法實作。
這類問題雖則本身沒有明顯的遞歸結構，但用遞歸求解比疊代求解更簡單，如hanoi問題。
(3)資料的結構形式是按遞歸定義的。
如二叉樹、廣義表等，由于結構本身固有的遞歸特性，則它們的操作可遞歸地描述。
遞歸的缺點：
遞歸算法解題相對常用的算法如普通循環等，運作效率較低。是以，應該盡量避免使用遞歸，除非沒有更好的算法或者某種特定情況，遞歸更為适合的時候。在遞歸調用的過程當中系統為每一層的傳回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。
遞歸典型問題： 梵塔問題（漢諾塔問題）
已知有三根針分别用a, b, c表示，在a中從上到下依次放n個從小到大的盤子，現要求把所有的盤子
從a針全部移到b針，移動規則是：可以使用c臨時存放盤子，每次隻能移動一塊盤子，而且每根針上
不能出現大盤壓小盤，找出移動次數最小的方案.
[2]
<col>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
<code>/*name:hanoitower</code>
<code>*description:solvethehanoitowerproblembyrecursion</code>
<code>*/</code>
<code>#include<stdio.h></code>
<code>#include<stdlib.h></code>
<code>/*movenplates:from-->to,</code>
<code>*thebuffercanbeusedifneeded*/</code>
<code>inthanoi(intn,charfrom,charbuffer,charto)</code>
<code>{</code>
<code>if</code><code>(n==1)</code>
<code>/*movetheno.1platedirectly:from-->to*/</code>
<code>printf</code><code>(</code><code>"moveplate#%dfrom%cto%c\n"</code><code>,n,from,to);</code>
<code>/*theno.1plateismovedsoreturn*/</code>
<code>return0;</code>
<code>}</code>
<code>else</code>
<code>/*nplatestobemoved:from-->to,</code>
<code>*movethen-1platesabove:from-->buffer,</code>
<code>*givethistasktothenextrecursion*/</code>
<code>hanoi(n-1,from,to,buffer);</code>
<code>/*then-1platesaboveweremovedtobuffer,</code>
<code>*sotheno.nplatecanbemoveddirectly*/</code>
<code>/*howeverthen-1platesarestillinbuffer,</code>
<code>*movethemtotheterminalposition,</code>
<code>*(the"from"positionhasnoplate,&canbeoneso-calledbuffer)*/</code>
<code>hanoi(n-1,buffer,from,to);</code>
<code>/*thetaskgivenisdonesoreturn*/</code>
<code>intmain()</code>
<code>#definen4</code>
<code>/*nplatesina,let'smovethemtoc*/</code>
<code>hanoi(n,</code><code>'a'</code><code>,</code><code>'b'</code><code>,</code><code>'c'</code><code>);</code>
如：
<code>//pascal</code>
<code>procedurea;</code>
<code>begin</code>
<code>a;</code>
<code>end;</code>
這種方式是直接調用.
又如：
<code>procedureb;</code>
<code>c;</code>
<code>procedurec;</code>
<code>b;</code>
這種方式是間接調用.
例1計算n!可用遞歸公式如下：
1 當 n=0 時
fac(n)={n*fac(n-1) 當n>0時
可編寫程式如下：
<code>programfac2;</code>
<code>var</code>
<code>n:integer;</code>
<code>functionfac(n:integer):real;</code>
<code>ifn=0thenfac:=1elsefac:=n*fac(n-1)；</code>
<code>write(</code><code>'n='</code><code>);readln(n);</code>
<code>writeln(</code><code>'fac('</code><code>,n,</code><code>')='</code><code>,fac(n):6:0);</code>
<code>end.</code>
例2 樓梯有n階台階，上樓可以一步上1階，也可以一步上2階，編一程式計算共有多少種不同的走法.
設n階台階的走法數為f(n)
顯然有
1 n=1
f(n)={2 n=2
f(n-1)+f(n-2) n>2
可程式設計式如下：
<code>programlouti;</code>
<code>varn:integer;</code>
<code>functionf(x:integer):integer;</code>
<code>ifx=1thenf:=1else</code>
<code>ifx=2thenf:=2elsef:=f(x-1)+f(x-2);</code>
<code>write(</code><code>'n='</code><code>);read(n);</code>
<code>writeln(</code><code>'f('</code><code>,n,</code><code>')='</code><code>,f(n))</code>
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,處理結束.
程式如下：
<code>programkspv;</code>
<code>a:array[0..10000]oflongint;</code>
<code>i,n:integer;</code>
<code>procedurequicksort(l,r:longint);</code>
<code>vari,j,mid:longint;</code>
<code>i:=l;j:=r;mid:=a[(l+r)div2];</code>
<code>repeat</code>
<code>whilea[i]<middoinc(i);</code>
<code>whilea[j]>middodec(j);</code>
<code>ifi<=jthen</code>
<code>a[0]:=a[i];a[i]:=a[j];a[j]:=a[0];</code>
<code>inc(i);dec(j);</code>
<code>untili>j;</code>
<code>ifi<rthenquicksort(i,r);</code>
<code>ifl<jthenquicksort(l,j);</code>
<code>write(</code><code>'inputdata:'</code><code>);</code>
<code>readln(n);</code>
<code>fori:=1tondoread(a[i]);</code>
<code>writeln;</code>
<code>quicksort(1,n);</code>
<code>write(</code><code>'outputdata:'</code><code>);</code>
<code>fori:=1tondowrite(a[i],</code><code>''</code><code>);</code>
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)