遞歸（計算機科學）

遞歸指的是，一個函式不斷引用自身，直到引用的唯一已知對象時止的過程。

使用遞歸解決問題，思路清晰，代碼少。

河內塔問題，是已知的，在編程方面只能用遞歸解決的問題。

其它可能用到遞歸解決的問題有菲波納契數列。

以下為求河內塔問題的Pascal程式：

procedure Hanoi(n:integer;x,y,z:char);

begin

if n<>1 then writeln(x,'-',n,'->',z)

else begin

Hanoi(n-1,x,z,y);

writeln(x,n,z);

Hanoi(n-1,y,x,z);

else writeln(x,n,z);

end;

end;

上述程式用接近自然語言的偽代碼可表述如下：

Hanoi 過程 (整型參數 n; 字元型參數 x,y,z);

//註：n 代表本步中要處理的盤子數，x,y,z 分別表示 n 號盤子原來所在柱子、經由柱子、目標柱子

開始

如果 n 不為 1 ，那么：開始

調用 Hanoi 過程 (參數為 n-1,x,z,y);

//註：這一步表示用本過程方法將剩餘 n-1 個盤子從柱子 x 經由柱子 z 移動到柱子 y

輸出 x,n,z; //註：表示將 n 號盤子從 x 移動到 z

調用 Hanoi 過程 (參數為 n-1,y,x,z);

//註：這一步表示用本過程方法將剩餘 n-1 個盤子從柱子 y 經由柱子 x 移動到柱子 z

結束; //以上程式段就完成了把 n 個盤子從柱子 x 經由柱子 y 移動到柱子 z

否則 輸出 x,n,z; //註：若 n 為1 的話本句直接輸出表示將 n 號盤子從 x 移動到 z

結束;