什么是递归

递归算法是一种直接或者间接调用自身函数或者方法的算法。

写代码也大半年了，平时在写代码时大多数情况下都用的循环，循环非常符合人的正向思维，先把整个循环过程构思好，给出初值、循环体、循环结束的条件再开始跑；最近看了一下递归，大惊，递归这种操作不正是我这种懒狗的福音吗，把一个复杂的问题抽象成只考虑解决其中的某一环和当这个问题被剥离成很简单的问题时的求解，如果说有什么其他的形式与递归相似的话，那就是数学归纳法了，不需要顺着从1推到n使等式成立，而是只需弄清n如何推导到n+1和n=1时成立就可以直接得出结论。

递归算法经典例子

汉诺塔问题

传说越南河内某间寺院有三根银棒，上串 64 个金盘。寺院里的僧侣依照一个古老的预言，以下述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。

有三根杆子A，B，C。A杆上有穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

1. 每次只能移动一个圆盘；
2. 大盘不能叠在小盘上面。

大概在我上小学的时候，手机还不是很普及，玩过的前几个手机游戏就有汉诺塔，当时觉得这游戏巨难，根本不懂怎么移才能达成目标，就算把其他俩游戏玩腻了都不玩这个（当然现在也还不会）。

其实这个问题想要直接解决推出每个步骤是非常困难的，根据蒙的经验，我们先写几行看看规律

• n=1时，直接把盘从A移到C，解决！
• n=2时，把1盘从A移到B，再把2盘从A移到C，再把1盘从B移到C，解决！
• n=3时，根据n=2的结论，先把1和2从A移到B，再把3从A移到C，再把1和2从B移到C，解决！

通过n=2和n=3的相似性大概已经可以看出操作的规律了

• n=n时，根据n-1的结论，先把1到n-1从A移到B，再把n从A移到C，再把1到n-1从B移到C，解决！

void hannoi (int n, char from, char buffer, char to)
{
    if (n == 0)
        return;
    hannoi (n - 1, from, to, buffer);
    Console.WriteLine("Move disk " + n + " from " + from + " to " + to);
    hannoi (n - 1, buffer, from, to);
}

通过递归的代码可以看出，通过递归实现的代码量是非常小的，汉诺塔问题如果要我通过循环解决，我还真不知道循环体和循环条件该怎么设置，递归简直就是救星，不过递归虽然简化了人的思考过程，但对于程序来说调用方法的次数太多了，对于栈空间的消耗非常大，入栈出栈的操作也非常多，代码的执行效率可能会大大降低。