前言

上章节讲到C语言的函数,详细内容请参见上章节。本章节主要是给大家介绍下C语言函数中的难点函数递归。

递归概念

在C语言中，函数调用可以从main（）函数，其他函数或同一函数本身进行。递归函数定义如下：一个函数调用函数自身称为递归函数。应该非常小心地使用递归函数，因为当一个函数自己调用它进入无限循环时。当函数进入无限循环时，函数执行永远不会完成。我们应该定义退出函数调用的条件，以便递归函数终止。当一个函数被自己调用时，第一个调用仍在执行中，直到调用最后一个调用。每次调用函数调用时，该函数都会将执行控件返回到上一个函数调用。举个栗子，你用你手中的钥匙打开一扇门，结果却发现前方还有一扇门，紧接着你又用钥匙打开了这扇门，然后你又看到一扇门...但是当你开到某扇门时，发现前方是一堵墙无路可走了，你选择原路返回——这就是递归，如下图即使是递归。

从阶乘看递归

阶乘是基斯顿·卡曼（Christian Kramp，1760～1826）于 1808 年发明的运算符号，是数学术语。一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!。1808年，基斯顿·卡曼引进这个表示法。亦即n!=1×2×3×...×n。阶乘亦可以递归方式定义：0!=1，n!=(n-1)!×n。

在上面的示例程序中，factorial（）函数调用是从main（）函数启动的，其值为3.在factorial（）函数内，函数调用factorial（2），factorial（1）和factorial（0）被调用递归。在该程序执行过程中，函数调用factorial（3）仍在执行中，直到函数调用factorial（2），factorial（1）和factorial（0）的执行完成。类似地，函数调用factorial（2）仍在执行中，直到函数调用factorial（1）和factorial（0）的执行完成。以相同的方式，函数调用factorial（1）保持执行，直到函数调用factorial（0）的执行完成。上述程序的完整执行过程如下图所示：

递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。可以试试factorial(1000)。

解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。尾递归是指，在函数返回的时候，调用自身本身，并且，return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。

可以看到，return fact_iter(n- 1, n* result)仅返回递归函数本身，n- 1和n* result在函数调用前就会被计算，不影响函数调用。尾递归调用时，如果做了优化，栈不会增长，因此，无论多少次调用也不会导致栈溢出。

尾言

使用递归函数的优点是逻辑简单清晰，缺点是过深的调用会导致栈溢出。针对尾递归优化的语言可以通过尾递归防止栈溢出。尾递归事实上和循环是等价的，没有循环语句的编程语言只能通过尾递归实现循环。标准的解释器没有针对尾递归做优化，任何递归函数都存在栈溢出的问题。

作业:

汉诺塔的移动可以用递归函数非常简单地实现。

请编写move(n, a, b, c)函数，它接收参数n，表示3个柱子A、B、C中第1个柱子A的盘子数量，然后打印出把所有盘子从A借助B移动到C的方法。

骏马是跑出来的,强兵是打出来的。驾驭命运的舵是奋斗。不抱有一丝幻想,不放弃一点机会,不停止一日前进脚步。