c语言中的递归

本人学c++，c的语法已经淡忘了，但是递归不管什么语言都是一个原理

创新互联公司主要业务有网站营销策划、网站设计制作、成都做网站、微信公众号开发、成都小程序开发、H5场景定制、程序开发等业务。一次合作终身朋友，是我们奉行的宗旨；我们不仅仅把客户当客户，还把客户视为我们的合作伙伴，在开展业务的过程中，公司还积累了丰富的行业经验、营销型网站建设资源和合作伙伴关系资源，并逐渐建立起规范的客户服务和保障体系。 

其实简单一点来说就像数学里面的数列的通项公式：

例如一个数列是2，4，6，8，10......

很容易就可以得到通项公式是a[n]=2*n n是大于0的整数

你肯定学过这个数列的另外一种表示方式就是： a[1]=2, a[n]=a[n-1]+2 n是大于1的整数

其实这就是一个递归的形式，只要你知道初始项的值，未知项和前几项之间的关系就可以知道整个数列。

程序例子：比如你要得到第x项的值

普通循环：

for(int i=1; i=n; i++)

if (i == x)

cout 2*i; /*cout 相当于 c里面的printf,就是输出.*/

递归：

int a(int x) {

if (x = 1)

return 2; /* 第一项那肯定是2了，这个也是递归的终止条件！ */

else return a(x-1)+2; /* 函数自身调用自身是递归的一个特色 */

比如x=4,那么用数学表示就是a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2

其实递归方法最接近自然，也是最好思考的一个方法，难点就是把对象建模成递归形式，但是好多问题本身就是以递归形式出现的。

普通递归就是数据结构上的堆栈，先进后出。

例如上面x=4,把a(4)放入栈底，然后放入a(3),然后a(2),a(1),a(1)的值已知，出栈，a(1)=2,a(2)出栈a(2)=a(1)+2=2+2=4,a(3)出栈a(3)=a(2)+2=(a(1)+2)+2=6,a(4)出栈a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2=8

再比如楼上的阶乘例子，当n=0 或 1时,0!=1,1!=1,这个是阶乘的初始值，也是递归的终止条件。然后我们知道n!=n*(n-1)!,当n1时,这样我们又有了递归形式，又可以以递归算法设计程序了。（楼上已给出谭老的程序，我就不写了）。

我给出一种优化的递归算法---尾递归。

从我给出的第一算法可以看出，先进栈再出栈，递归的效率是很低的。速度上完全比不上迭代（循环）。但是尾递归引入了一个新的函数参数，用这个新的函数参数来记录中间值.

普通递归阶乘fac(x),就1个x而已，尾递归用2个参数fac(x,y),y存放阶乘值。

所以谭老的程序就变成

// zysable's tail recursive algorithm of factorial.

int fac(int x, int y) {

if (x == 1)

return y;

else return fac(x-1, y*x);}

int ff(int x) {

if (x == 0)

return 1;

else return fac(x,1);}

对于这个程序我们先看函数ff，函数ff其实是对fac的一个封装函数，纯粹是为了输入方便设计的，通过调用ff(x)来调用fac(x,1),这里常数1就是当x=1的时候阶乘值了，我通过走一遍当x=3时的值即为3!来说明一下。

首先ff(3),x!=0,执行fac(3,1).第一次调用fac，x=3,y=1,x!=1,调用fac(x-1,y*x),新的x=2,y=3*1=3,这里可以看到，y已经累计了一次阶乘值了，然后x还是!=1,继续第三次调用fac(x-1,y*x),新的x=1,y=2*3=6,然后x=1了，返回y的值是6，也就是3！.你会发现这个递归更类似于迭代了。事实上我们用了y记录了普通递归时候，出栈的乘积，所以减少了出栈后的步骤，而且现在世界上很多程序员都在倡议用尾递归取消循环，因为有些在很多解释器上尾递归比迭代稍微效率一点.

基本所有普通递归的问题都可以用尾递归来解决。

一个问题以递归来解决重要的是你能抽象出问题的递归公式，只要递归公式有了，你就可以放心大胆的在程序中使用，另外一个重点就是递归的终止条件；

其实这个终止条件也是包含在递归公式里面的，就是初始值的定义。英文叫define initial value. 用普通递归的时候不要刻意让自己去人工追踪程序，查看运行过程，有些时候你会发现你越看越不明白，只要递归公式转化成程序语言正确了，结果必然是正确的。学递归的初学者总是想用追踪程序运行来让自己来了解递归，结果越弄越糊涂。

如果想很清楚的了解递归，有种计算机语言叫scheme,完全递归的语言，因为没有循环语句和赋值语句。但是国内人知道的很少，大部分知道是的lisp。

好了，就给你说到这里了，希望你能学好递归。

PS:递归不要滥用，否则程序极其无效率，要用也用尾递归。by 一名在美国的中国程序员zysable。

C语言的函数嵌套调用与函数递归调用有啥区别？

需要明白的是

函数嵌套是语言特性，递归调用是逻辑思想。

函数嵌套允许在一个函数中调用另外一个函数，比如有三个函数

funca()

{

funcb();

}

funcb()

{

funcc();

}

funcc()

{

cout "Hello" endl;

}

这个就叫做嵌套调用，它是一个语言提供的程序设计的方法，也就是语言的特性。

而递归是一种解决方案，一种思想，将一个大工作分为逐渐减小的小工作，比如说一个和尚要搬50块石头，他想，只要先搬走49块，那剩下的一块就能搬完了，然后考虑那49块，只要先搬走48块，那剩下的一块就能搬完了……，递归是一种思想，只不过在程序中，就是依靠函数嵌套这个特性来实现了。

递归最明显的特点就是，自己调用自己（不就嵌套调用了嘛）。

funca()

{

if(statement1)

funca();

else

exit(0);

}

概括说，函数嵌套就是函数调用函数，是普遍的，递归就是函数调用自身，使函数嵌套的一个特例。

我说的不知道明不明白，有点乱……

用C语言的递归解决分鱼问题

下面代码是我自己写的，看别人代码比较累，所以如果楼主愿意，可以看看下面的代码，我会尽量讲解细致一点。

#include stdio.h

//sub(manth,fishleft)参数意义：manth表示第几个人分鱼，fishleft表示他分鱼时获得了多少鱼

//函数的返回结果是第manth个人分鱼时剩余的条数，如manth = 5，fishleft = 1，则表示一共捕获了3906条鱼。

int sub(int manth,int fishleft){

if(manth == 1){

fishleft = (5*fishleft +1);

printf("manth = %d,fishleft = %d\n",manth,fishleft);

return fishleft;

}

fishleft = 5*sub(--manth,fishleft)+1;

printf("manth = %d,fishleft = %d\n",manth+1,fishleft);

return fishleft;

}

int main(void){

int manth = 5;

int fishleft = 1;

printf("%d\n",sub(5,1));

return 0;

}

//我得到的结果和楼主所给程序运行结果不一致！楼主可以自己计算，如果最后一个人得到的是1条鱼，则他分鱼时应该剩余6条，manth = 2时应该剩余6*5+1 = 31条，manth = 3时，应该剩余31*5+1条，最后manth= 5，也就是分鱼开始的时候，应该剩余3906条鱼。

//楼主可以用自己的程序测试，当调用sub(2)时得到的是21，而不是31，就能证明该程序应该是用问题的。

文章名称：c语言函数递归谭浩强 c语言函数的递归调用是什么
标题来源：http://chengdu.cdxwcx.cn/article/dopocos.html