（一）递归

        递归是函数对自己的调用，递归一定有一个退出条件，不然会陷入死循环。

        看一个最简单的例子，要求倒序输出N，N-1....0到屏幕上，使用递归。

递归

        函数重复调用自己，这里有一个退出条件，就是 n 等于 0时，退出函数。

其实递归是分步骤处理一个问题，且每个问题都有相同的规律。

典型的一个问题是斐波那契数列，1、1、2、3、5、8、13、21、34、……其规律是最开始2个数是1，从第三个数开始的值是前2个数的和。如果定义第N步是 函数  fbLIst(n), 则    fbLIst(n)=  fbLIst(n-1)+  fbLIst(n-2)，很明显可以用递归处理，这里退出条件是当n等于1或者2的时候，都返回1，代码如下

斐波那契数列

再复杂一点的则是汉诺塔问题：

汉诺塔

将A上的所有盘移动到C，每次只能移动一片，大片不能压在小片上。

图示为4层汉诺塔解法：

汉诺塔

可以看到有几个关键的步骤:  

》 将N-1个盘借助最后的盘（c）先移到中间的盘（b），再把大盘从从第一个盘（a）移到最后的盘（c）

关键步骤1

》再借助a, 把第n-1个盘从b移动到c

关键步骤2

这时候，其实又变成了上面那一步了，将a上的2个盘移动到c盘，

到此汉诺塔问题已经被分解成了2个关键步骤：

1.将a上的除最大盘子外的盘子移动到b，再将a上最大的盘子移动到c

2.将b上的除最大盘子外的盘子移动到a，再将b上最大的盘子移动到c

最后一步是用递归的方式，处理任意多个盘子的汉诺塔问题

我们定义一个移动函数 moveHNT(n int, x,y,z string)  输入盘子数和3根杆子,用这个函数来解决汉诺塔问题， 代码如下

汉诺塔 输出结果