河内塔(THE TOWER OF HANOI)描述的递归原理

河内塔是有国数学家爱德华·卢卡斯于1883发明的．给定一个由8个圆盘组成的塔，这些圆盘按照大小递减的方式套在三根桩柱中的一根上．

我们先以最少的大小两个圆盘来说

T 0 =0

T n =2T n-1 +1

正常的递归公式已经完成。我们可以进一步进行公式演算(数学归纳法)

T 0 +1=1

T n +1=2T n-1 +2

如果令U n =T n +1,那么就有

U n =2U n-1 =>U n =2 n

如是推导出