盧卡斯用關於Brahma塔的浪漫傳說裝扮他的玩具，而Brahma塔有著64個純金的圓碟片放在3個鑽石的針頭上。他說一開始上帝把這些純金的圓碟片放在第一個針頭上，並且安排一些教士根據以上的規則去將它們轉移到第三個針頭上。教士們傳說工作了日日夜夜。當他們完成這項任務時，這個塔就會崩潰並且世界也將走到終點。
這個難題有一個方案但並不是立刻就明顯的，但有一點想法使我們信服它完全可行。現在問題提升為：我們能做的最好的是什麼呢？那就是執行這個任務到底有多少次移動是必要和充足的。
處理這個問題的最好方式就是像這樣去歸納為一點。Brahma塔有64個圓碟片，河內塔有8個圓碟片；先來考慮如果這裡有n個圓碟片會發生什麼。
這樣歸納的一個優點是我們可以處理更多這樣的問題。事實上，我們將在這本書中反復看到“先觀察最小案例”的優點。轉移包含一個或兩個圓碟片的塔是很輕松的。而小數目的案例的實驗展示了怎樣去轉移。
解決問題的下一步是介紹合適的記號：命名和征服。假設在盧卡斯的規則下從一個楔子將圓碟片移動到另一個楔子的最小移動次數是Tn。那麼T1明顯是1，T2明顯是3。
我們還可以輕松的得到另一組數據，通過考慮其中最小的案例：T0=0,因為0個圓碟片的塔畢竟不需要移動。聰明的數學家並不羞愧與思考簡單的案例，因為當極端的案例可以很好的理解時（甚至它們是不重要的）普遍的模式更容易意識到。
但現在來轉變我們的觀點來試著往大的方向思考，怎樣去移動一個較大的塔呢？有3個圓碟片的塔的實驗告訴我們贏得這一想法就是去移動最上面的2個圓碟片到中間的楔子上，然後移動第三個楔子，最後將中間楔子上的2個圓碟片移到第三個楔子上。這給了我們移動普遍上n個圓碟片的線索：我們可以最開始移動n-1個最小的圓碟片到另一個楔子上（需要Tn-1步），然後移動最大的圓碟片（需要1步），最好移動n-1個最小的圓碟片到最大的圓碟片上（需要另外Tn-1步）。因此我們可以轉移n個圓碟片（n>0)通過最多2Tn-1+1步：
Tn<=2Tn-1+1, for n>0.
這個公式用“<=”代替“=”，因為我們僅僅證明了2Tn-1+1步是足以的；我們還沒有展示這是必須的。一個聰明的人可能有能力想到一個捷徑。
但是這是最好的方式嗎？當然不是。在一些觀點中我們必須移動最大的圓碟片。當我們這樣做的時候，n-1個最小的圓碟片必須在一個單獨的楔子上，並且這已經花費了至少Tn-1步去移動。如果我們不夠警覺，我們可能移動最大的圓碟片不止一次。但是當上一次移動了一個圓碟片之後，我們必須移動n-1個最小的圓碟片（那必須再次處在單獨的楔子上）返回到最大的圓碟片上；這同樣花費了Tn-1步。因此：
Tn>=2Tn-1+1, for n>0.
這裡和n=0的方案有一個不平衡，提出
T0 = 0;
Tn = 2Tn-1+1, for n>0. （1.1）
（注意到這三個公式和已知的T1=1，T2=2是一致。我們最小案例不僅僅幫我們發現了一個普遍的公式，還提供了一個簡便的方法去檢查我們有沒有犯愚蠢的錯誤。尤其是以後當我們在後面的章節中遇到更復雜的問題是可以作為特殊值檢查。）
像（1.1）這一套等式叫做遞歸。它從最早的方面給普遍值一個邊界和等式。有時候我們單獨引用一個普遍的等式作為遞歸，盡管嚴格意義上需要一個邊界值去補充。
遞歸允許我們去計算對於任何n值的Tn。但是當n很大時沒有人想去從遞歸中計算，因為這需要花費很長時間。遞歸僅僅提供了間接的本地的消息。而關於遞歸的一個解決方案或許會更好些。那就是我們想要一個好的有序的“closed form”給遞歸，因為這讓我們計算得更快，即便是對於一個很大的n值。有一個封閉的列表我們就能知道Tn真正是什麼。
所以我們到底怎樣去解決一個遞歸呢？一個路徑是去猜想正確的解決方案然後去證明它。但我們最希望的則是去根據更小的案例來猜想解決方案。所以我們的計算會很快速。
T3 =2*3 +1 =7;
T4 =2*7 +1 =15;
T5 =2*15+1 =31;
T6 =2*31+1 =63.
這明顯看起來像是
Tn =2^n-1 for n >=0. （1.2）
至少對於n<=6成立。
數學歸納法就是一個普遍的方法去證明一些關於一個正整數對於所有的n>=n0是正確的陳述。首先我們證明當n有它最小值的陳述，這被稱為基點。然後我們證明對於n>n0，假設它已經被證明在所有的n和n-1之間成立。所以這樣一個結論只要很少數據的證明工作就可以得出極大量的結果。
遞歸最好地建立了數學歸納法。在我們的案例中，（1.2）輕松的從（1.1）得來：基點是不重要的，自從T0=2^0-1=0。而且結論遵循對於n>0如果我們假設（1.2）當n被替代為n-1時不變。
Tn =2Tn-1+1 =2(2^(n-1)-1)+1 =2^n-1.
因此（1.2）對於n也保持不變。我們對於Tn的探索已經成功結束了。
當然教士的任務還沒有完成，他們仍然附和地移動著圓碟片，並將持續好一陣子。因為對於n=64來說，這裡有2^64-1步（大約1844.6億億）。即便以不可能的速率，每微秒移動一步，他們也需要超過5000世紀來移動Brahma塔。盧卡斯最初的難題則是更實際的。它需要2^8-1=255步，較快的話只需要4分鐘。
河內塔遞歸是出現在各種各樣的應用程序典型的一個。在發現封閉列表對於興趣就像Tn，我們通過3個階段：
1 觀察最小的案例。這給予我們洞察力已經幫助我們在第2第三3階段。
2 發現和證明一個數學表達式對於大量實例。對於河內塔，這是一個允許我們計算對於任何n的Tn的遞歸。
3 發現和證明一個封閉列表從我們的數學表達式中。對於河內塔，這就是一個遞歸的解決方案。
第三階段是將貫穿於本書的精神。事實上，我們將頻繁的略過第1和第2階段，因為數學表達式講被當成一個起點。但是即使那樣，我們也將在問題之下通過所有的3個階段來入手。
我們關於河內塔的分析引導出了正確的結果，但它被要求了一個“歸納的跳躍”；我們信賴於答案的一個幸運的猜想。本書的主要目標之一就是去解釋一個人怎樣解決遞歸問題而不需要驚人的洞察力。例如，我們將看到（1.1）中的遞歸可以被簡化，通過等式兩邊加1：
T0+1=1;
Tn+1=2Tn-1+2, for n >0.
現在我們假設Un=Tn+1,因此有
U0=1;
Un=2Un-1+1, for n >0.
這很容易地發現對於這個遞歸的解決方案僅僅是Un=2^n，因此Tn=2^n-1。即使一個計算就可以發現它。
該算法中，通過比較數組中相鄰的（奇-偶）位置數字對，如果該奇偶對是錯誤的順序（第一個大於第二個），則交換。下一步重復該操作，但針對所有的（偶-奇）位置數字對。如此交替進行下去。
Python語言
# 假設已有列表a等待排序
while True:
sorted = True
# 處理奇-偶對
for i in xrange(1,
len(a)-1,
2):
if a[i] > a[i+1]: a[i], a[i+1]
= a[i+1], a[i]
# 交換
sorted = False
# 處理偶-奇對
for i in xrange(0,
len(a)-1,
2):
if a[i] > a[i+1]:
a[i], a[i+1]
= a[i+1], a[i]
# 交換
sorted = False
if sorted:
break
JavaScript語言
/* 假設已有數組a等待排序 */
var sorted = false;
while(!sorted)
{
sorted=true;
for(var i = 1; i
< list.length-1; i
+= 2)
{
if(a[i] > a[i+1])
{
swap(a, i, i+1);
sorted = false;
}
}
for(var i = 0; i
< list.length-1; i
+= 2)
{
if(a[i] > a[i+1])
{
swap(a, i, i+1);
sorted = false;
}
}
五、快速排序
快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。
步驟為：
從數列中挑出一個元素，稱為 "基准"（pivot），重新排序數列，所有元素比基准值小的擺放在基准前面，所有元素比基准值大的擺在基准的後面（相同的數可以到任一邊）。在這個分割結束之後，該基准就處於數列的中間位置。這個稱為分割（partition）操作。遞歸地（recursive）把小於基准值元素的子數列和大於基准值元素的子數列排序。遞回的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞回下去，但是這個演算法總會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。
C#實現
static void Main(string[] args)
{
int[] a = new int[] { 10, 22, 30, 3, 31, 5, 36, 68, 103, 90, 100, 93 };
for (int i = 0; i < 7; i++)
{
Console.Write(a[i]+" ");
}
Console.WriteLine();
Sort(a, 0, 6);
for (int i = 0; i < 7; i++)
{
Console.Write(a[i] + " ");
}
}
public static void Sort(int[] numbers)
{
Sort(numbers, 0, numbers.Length - 1);
}
private static void Sort(int[] numbers, int left, int right)
{
if (left < right)
{
int middle = numbers[(left + right) / 2];
int i = left - 1;
int j = right + 1;
while (true)
{
while (numbers[++i] < middle) ;
while (numbers[--j] > middle) ;
if (i >= j)
break;
Swap(numbers, i, j);
}
Sort(numbers, left, i - 1);
Sort(numbers, j + 1, right);
}
}
private static void Swap(int[] numbers, int i, int j)
{
int number = numbers[i];
numbers[i] = numbers[j];
numbers[j] = number;
}
六、直接插入法
C#實現
static void Main(string[] args)
{
int temp;
int[] a = new int[10] { 12, 23, 32, 15, 73, 30, 09, 20, 90, 85 };
for(int i=0;i
{
temp = a[i];
int j = i;
while((j>0)&&(a[j-1]>temp))
{
a[j] = a[j - 1];
j -= 1;
}
a[j] = temp;
}
foreach(int i in a)
{
Console.Write(i+" ");
}
}
七、希爾排序法
希爾排序又稱“縮小增量排序”，其基本思想是，先將整個待排序的一組序列分割成為若干子序列，然後分別進行直接插入排序，待整個序列中的數“基本有序”時再對全體記錄進行一次直接插入排序。
C#實現
static void Main(string[] args)
{
int[] a = new int[10] { 12, 23, 32, 15, 73, 30, 09, 20, 90, 85 };
if(a!=null)
{
int inc;
for (inc = 1; inc <= a.Length / 9; inc = 3 * inc + 1) ; // 截斷序列
for(;inc>0;inc/=3)
{
for(int i=inc+1;i<=a.Length;i+=inc)
{
int temp = a[i - 1]; // 記錄當前值
int j = i; // 定義下一個索引
while((j>inc)&&(a[j-inc-1]>temp))
{
a[j - 1] = a[j - inc - 1];
j -= inc;
}
a[j - 1] = temp; // 將下一個元素值設置為當前值
}
}
foreach(int i in a)
{
Console.Write(i + " ");
}
}
}
