聂卫平 知乎:递归函数是什么意思

说的太多反而不清楚是什么
回答问题最好不要复制粘贴。。。
递归就是一个函数内出现调用本身的现象，举个最简单的例子，求阶乘：
当n=0或1时，n！=1；当n>1时，n！=n*(n-1)!通过这样的思想，程序写为：
int fun(int n)
{
if(n<2)
return 1;
else
return n*fun(n-1);
}
看到了fun函数内调用了它本身fun，可以想象一步步下去就可以得到计算结果。

很多初学者往往对递归迷惑不解，也在这上面花了不少的时间。其实教材上的例子很经典，只是它说的有一些唠叨了。初学者会看的头大的。编程是解决问题的，而现实中很多的问题都是比较简单的，没有象汉诺塔那么复杂。我们也不必追究递归到底是怎样实现的，我们只是要会用递归，会用递归来为我们解决一些问题，这就行了。

首先来看一个例子：

有一个Febonacci序列：

1,1,2,3,5,8,13,,21,34........

它的问题是：求这个序列中的第N个数。

由于它的函数原形是：f(n)=f(n-1)+f(n-2)

这用递归很容易就可以写出代码来，一点都不费事：

int Febc(int n) {

if(n<3) return (1);

else

return (Febc(n-1)+Febc(n-2));

}

噢~~~~~也许你会说递归真是太简单了，简直就是一个数学模型嘛，呵呵。

其实，递归函数的工作过程就是自己调用自己。有一些问题用递归就很容易解决，简单的你自己都会吃惊。

我们做事情，一般都是从头开始的，而递归却是从末尾开始的。比如上面的函数吧，当n>3时，它显然只能求助于n-1,n-2。而(n-1)>2,(n-2)>2时，它们就求助于：(n-1)-1,(n-1)-2;(n-2)-1,(n-2)-2;然后··············直到（n-k)<3,(n-k-1)<3时，函数Febc终于有了返回值1 了，它再从头开始计算，然后一直算到n 为止。

通过上面的例子，我们知道递归一定要有一个停止的条件，否则递归就不知道停止了。在上面的例子中， if(n<3) return (1); 就是停止的条件。

然而，使用递归的代价是十分巨大的：它会消耗大量的内存！！递归循环时它用的是堆栈，而堆栈的资源是十分有限的。上面的例子你只能用一个很小的n值。如果n=20，即Febc(20)的话，它将调用Febc(n)函数10000多次！！！而上面一个例子用循环也是十分容易写的：

/*using turboc2*/
int febc(int);
main()
{
int n;
scanf("%d",&n);
febc(n);
}

int febc(int n)
{
int a[3],i;
a[0]=a[1]=a[2]=1;
for(i=3;i<=n;i++)
a[i%3]=a[(i+1)%3]+a[(i+2)%3]; /*实现 Febc(i)=Febc(i-1)+Febc(i-2)*/
printf("\n%d\n",a[n%3]);
}

有兴趣者不妨输入一个较大的n值，然后比较比较这二个函数计算的速度。当然， 如果你使用的n太大的话，递归可能发生错误。如果死机了可别骂我哦~~~ 我已经提醒过你了 ：）

现在我们再来看看一个求从1 加到100的循环：

/*turboc2*/

main()

{ int i,n;

for(i=1;i<101;i++)

n+=i; }

这很简单没什么可说的。 但是，你能不能写出相应的递归函数呢？

递归是一种重要的编程技术。该方法用于让一个函数从其内部调用其自身。一个示例就是计算阶乘。0 的阶乘被特别地定义为 1。 更大数的阶乘是通过计算 1 * 2 * ...来求得的，每次增加 1，直至达到要计算其阶乘的那个数。

下面的段落是用文字定义的计算阶乘的一个函数。

“如果这个数小于零，则拒绝接收。如果不是一个整数，则将其向下舍入为相邻的整数。如果这个数为 0，则其阶乘为 1。如果这个数大于 0，则将其与相邻较小的数的阶乘相乘。”

要计算任何大于 0 的数的阶乘，至少需要计算一个其他数的阶乘。用来实现这个功能的函数就是已经位于其中的函数；该函数在执行当前的这个数之前，必须调用它本身来计算相邻的较小数的阶乘。这就是一个递归示例。

递归和迭代（循环）是密切相关的 — 能用递归处理的算法也都可以采用迭代，反之亦然。确定的算法通常可以用几种方法实现，您只需选择最自然贴切的方法，或者您觉得用起来最轻松的一种即可。

显然，这样有可能会出现问题。可以很容易地创建一个递归函数，但该函数不能得到一个确定的结果，并且不能达到一个终点。这样的递归将导致计算机执行一个“无限”循环。下面就是一个示例：在计算阶乘的文字描述中遗漏了第一条规则（对负数的处理） ，并试图计算任何负数的阶乘。这将导致失败，因为按顺序计算 -24 的阶乘时，首先不得不计算 -25 的阶乘；然而这样又不得不计算 -26 的阶乘；如此继续。很明显，这样永远也不会到达一个终止点。

因此在设计递归函数时应特别仔细。如果怀疑其中存在着无限递归的可能，则可以让该函数记录它调用自身的次数。如果该函数调用自身的次数太多，即使您已决定了它应调用多少次，就自动退出。

下面仍然是阶乘函数，这次是用 JScript 代码编写的。

// 计算阶乘的函数。如果传递了
// 无效的数值（例如小于零），
// 将返回 -1，表明发生了错误。若数值有效，
// 把数值转换为最相近的整数，并
// 返回阶乘。
function factorial(aNumber) {
aNumber = Math.floor(aNumber); // 如果这个数不是一个整数，则向下舍入。
if (aNumber < 0) { // 如果这个数小于 0，拒绝接收。
return -1;
}
if (aNumber == 0) { // 如果为 0，则其阶乘为 1。
return 1;
}
else return (aNumber * factorial(aNumber - 1)); // 否则，递归直至完成。
}

楼上两位何必说得那么复杂!!
递归函数就是,一个函数自己调用自己本身(只是在调用时参数上有所不同).