❶ 尾递归的实例
为了理解尾递归是如何工作的，让我们再次以递归的形式计算阶乘。首先，这可以很容易让我们理解为什么之前所定义的递归不是尾递归。回忆之前对计算n!的定义：在每个活跃期计算n倍的(n－1)!的值，让n=n－1并持续这个过程直到n=1为止。这种定义不是尾递归的，因为每个活跃期的返回值都依赖于用n乘以下一个活跃期的返回值，因此每次调用产生的栈帧将不得不保存在栈上直到下一个子调用的返回值确定。现在让我们考虑以尾递归的形式来定义计算n!的过 程。
这种定义还需要接受第二个参数a，除此之外并没有太大区别。a（初始化为1）维护递归层次的深度。这就让我们避免了每次还需要将返回值再乘以n。然而，在每次递归调用中，令a=na并且n=n－1。继续递归调用，直到n=1，这满足结束条件，此时直接返回a即可。
代码实例3-2给出了一个C函数facttail，它接受一个整数n并以尾递归的形式计算n的阶乘。这个函数还接受一个参数a，a的初始值为1。facttail使用a来维护递归层次的深度，除此之外它和fact很相似。读者可以注意一下函数的具体实现和尾递归定义的相似之处。
示例3-2：以尾递归的形式计算阶乘的一个函数实现 /*facttail.c*/#includefacttail.h/*facttail*/intfacttail(intn,inta){/*Computeafactorialinatail-recursivemanner.*/if(n<0)return0;elseif(n==0)return1;elseif(n==1)returna;elsereturnfacttail(n-1,n*a);}示例3-2中的函数是尾递归的，因为对facttail的单次递归调用是函数返回前最后执行的一条语句。在facttail中碰巧最后一条语句也是对facttail的调用，但这并不是必需的。换句话说，在递归调用之后还可以有其他的语句执行，只是它们只能在递归调用没有执行时才可以执行 。 尾递归是极其重要的，不用尾递归，函数的堆栈耗用难以估量，需要保存很多中间函数的堆栈。比如f(n, sum) = f(n-1) + value(n) + sum; 会保存n个函数调用堆栈，而使用尾递归f(n, sum) = f(n-1, sum+value(n)); 这样则只保留后一个函数堆栈即可，之前的可优化删去。
也许在c语言中有很多的特例，但编程语言不只有C语言，在函数式语言Erlang中（亦是栈语言），如果想要保持语言的高并发特性，就必须用尾递归来替代传统的递归。
原文的说法是错误的：原文如下：
一种算法, 用于计算机编程技术.
尾递归是针对传统的递归算法而言的, 传统的递归算法在很多时候被视为洪水猛兽. 它的名声狼籍, 好像永远和低效联系在一起.
尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去.
以下是具体实例:
线性递归: longRescuvie(longn){return(n==1)?1:n*Rescuvie(n-1);}尾递归: longTailRescuvie(longn,longa){return(n==1)?a:TailRescuvie(n-1,a*n);}longTailRescuvie(longn){//封装用的return(n==0)?1:TailRescuvie(n,1);}当n = 5时
对于线性递归, 他的递归过程如下:
Rescuvie(5)
{5 * Rescuvie(4)}
{5 * {4 * Rescuvie(3)}}
{5 * {4 * {3 * Rescuvie(2)}}}
{5 * {4 * {3 * {2 * Rescuvie(1)}}}}
{5 * {4 * {3 * {2 * 1}}}}
{5 * {4 * {3 * 2}}}
{5 * {4 * 6}}
{5 * 24}
120
对于尾递归, 他的递归过程如下:
TailRescuvie(5)
TailRescuvie(5, 1)
TailRescuvie(4, 5)
TailRescuvie(3, 20)
TailRescuvie(2, 60)
TailRescuvie(1, 120)
120
很容易看出, 普通的线性递归比尾递归更加消耗资源, 在实现上说, 每次重复的过程
调用都使得调用链条不断加长. 系统不得不使用栈进行数据保存和恢复.而尾递归就
不存在这样的问题, 因为他的状态完全由n和a保存.
具体事例2 快速排序算法实施尾递归优化 voidquickSort(SqList*list,intlow,inthigh){intpivot;while(low<high){pivot=Partition(list,low,high);quickSort(list,low,pivot-1);//quickSort(list,low,pivot-1);原递归调用//quickSort(list,pivot+1,high);low=pivot+1;/*尾递归*/}}//
首先：尾递归是线性递归的子集，属于线性递归。具体概念请参阅各大高校出版的书籍。作者把概念搞错了
其次，上文所举的第二个例子中在TailRescuvie(n-1, 1)没有计算出来之前，是不能return的。也就是说递归过程和第一个例子是差不多的，根本没有节约资源，甚至更浪费。
其实，编译器会很容易的对尾递归使用跳转语句进行优化，其实是可以return的。
尾递归就是把当前的运算结果（或路径）放在参数里传给下层函数，深层函数所面对的不是越来越简单的问题，而是越来越复杂的问题——因为参数里带有前面若干步的运算路径。对于阶乘而言，越深并不意味着越复杂。
从时间和空间效率上看，尾递归和传统递归差不多。递归运算效率低主要是分支巨大，像阶乘这类单分支的递归，效率并不低。递归运算的深度和运算总量大致成指数关系，return多次并不会造成显着的性能损失。
一言以蔽之，传统递归越深，距离目标越近；尾递归越深，距离起点越远。
尾递归适用于运算对当前递归路径有依赖的问题，传统递归适用于运算对更深层递归有依赖的问题。
/**************************************************************************************************/
第二作者对第二个例子的解释上有点不全面，尾递归的效果就是去除了将下层的结果再次返回给上层，需要上层继续计算才得出结果的弊端，如果读者仔细观看第二例子就可以看出，其实每个递归的结果是存储在第二个参数a中的，到最后一次计算的时候，会只返回一个a的值，但是因为是递归的原理虽然仍然要返回给上层，依次到顶部才给出结果，但是不需要再做计算了，这点的好处就是每次分配的内存不会因为递归而扩大。
在效率上，两者的确差不多。
❷ 已知斐波那契数列前两项均等于1，用C语言编写求取斐波那契数列第n项的尾递归算法。
尾递归是一种混合了迭代和递归的算法，C语言代码如下：
/*斐波那契数列的尾递归写法*/
#include<stdio.h>
doublefib(doublen,doublea,doubleb)
{
if(n<=0.0)
return-1.0; //错误输入
elseif(n==1.0||n==2.0)
returnb; //b记录最靠后的一项
else
{
while(n>2.0)
returnfib(n-1.0,b,a+b);
}
}
intmain(intargc,char*argv[])
{
doubled,n=20.0;
d=fib(n,1.0,1.0);
printf("斐波那契数列第%.f项的值为%.f。 ",n,d);
return0;
}
❸ 关于C中的递归和递推有点晕，新手多包涵
我想你要说的是递归和循环（从程序执行角度，递推比较侧重逻辑推理）。递归可以看作一个逆向求解的过程，循环则可以看作一个正向求解的过程。
unsigned long
fac0(int n)
{
return (n == 0 ? 1 : n * fac0(n-1));
}
unsigned long
fac1(int n)
{
int i;
unsigned long r;
for (r = 1, i = 1; i <= n; ++i)
r *= i;
return r;
}
fac0是用递归定义的，fac1是用循环定义的。两者字面上的区别就是，递归定义的函数体里面必然要自调用（在fac0的定义里面我们调用了fac0(n-1)），相反以循环定义的函数fac1里面却没有自调用。
递归与循环更深层次的区别则在执行的过程上。在一个没有提供尾调优化的编译器上，递归的执行效率比循环低很多，也就是说当输入很大时，循环实现将比递归实现更快地给出结果。为什么会这样呢？我们看一个计算fac0(3)和fac1(3)的比较：
fac0(3) = 3 * 调用fac0(3-1)，等待fac0(2)的返回值
fac0(2) = 2 * 调用fac0(2-1)，等待fac0(1)的返回值
fac0(1) = 1 * 调用fac0(1-1)，等待fac0(0)的返回值
fac0(0) = 1 fac0(0)直接返回1
fac0(1) = 1 拿到fac(0)的返回值1，算出1*1返回1
fac0(2) = 2 拿到fac0(1)的返回值1，算出2*1返回2
fac0(3) = 6 拿到fac0(2)的返回值2，算出3*2返回6
所以你看到递归实现会有一串调用返回的过程，正是这一频繁调用返回的过程将耗去很多的时间，而且伴有等待，这一等待也是有开销的，因为一般函数的调用和返回在底层是通过调用栈（call stack）实现的，当一个函数调用另一个函数时，调用函数要先把自己的当前状态保存到调用栈，然后跳到被调用函数体里面执行，等到那里执行完后，被调用函数返回，之前的调用函数才又从调用栈恢复。所以一条函数调用链越长，意味着将有越多的中间状态被保存到调用栈，如果输入很大，比如fac0(100)，就会生成一条很长的调用链fac0(100) --> fac0(99) --> ... --> fac0(0)，而调用栈的大小一般都有一个上限，这条调用链很可能还没有到达fac0(0)开始返回，中间需要保存的状态就已经超出这个上限了，于是就产生栈溢出（stack overflow）的错误。所以递归实现在空间效率上往往也表现糟糕。
相反，循环实现则没有上面提到的调用返回链的问题。所以在时间和空间效率上都略胜一筹。但是递归比循环适用范围广，也就是说有的算法用递归能实现，用循环却做不到（比如二叉树的遍历）。实际上，所有的循环都可以转化为一类特殊的递归，尾递归。而且，如果编译器能做尾调优化，那么用尾递归实现的算法在空间利用上则跟用循环实现持平。下面是阶乘用尾递归的实现：
unsigned long
fac2(int n, unsigned long r)
{
return (n == 0 ? r : fac2(n-1, n*r));
}
计算的时候要写fac2(3, 1);。
递归一开始是比较抽象的，要慢慢理解。如果我上面有些概念你不太明白也没太大关系，往后你会明白的。
❹ c语言可以实现尾递归吗
尾递归只是递归在算法实现上的一种资源优化方式，这个跟语言一点关系都没有。什么语言都可以实现。
❺ 在C语言中，是不是大多数递归问题都可以用循环来解决
理论上，所有循环都可以转化为递归，所有递归都可以转化为循环
当发现递归深度很深而造成栈空间耗尽时，可以用“循环+状态容器”的方法来代替
补充：理论上，尾递归是基本不损耗栈的（不会随着递归次数的增加而损耗栈空间），在C语言中只要打开尾递归优化编译选项就可以实现无限深度尾递归。
❻ c语言 以尾递归的方式计算整数2049的质因子
var a:array[0..100]of longint;
n,i:longint;
procere work(var n:longint;i:longint);
begin
while i*i<=n do
if n mod i=0 then
begin
n:=n div i;
if a[a[0]]<i then begin inc(a[0]); a[a[0]]:=i; end;
work(n,i);
end
else inc(i);
if (n>1)and(a[a[0]]<n) then begin inc(a[0]); a[a[0]]:=n end;
end;
begin
readln(n);
work(n,2);
for i:=1 to a[0]-1 do write(a[i],' ');
writeln(a[a[0]]);
end.
❼ C语言，数据结构，很简单的一个程序，尾递归转 非递归怎么算
#include<stdio.h>
int main()
{
int x,count=0;
int a[100],sum=0;
int i;
while(1)
{
printf("请输入一个数字");
scanf("%d",&x);
if(x==0)
{
a[count]=0;
for(i=count;i>=0;i--)
{
sum+=a[i];
printf("%d ",sum);
}
break;
}
else
{
a[count++]=x;
}
}
return 0;
}
依次输入4,5,6,0
结果为 0,6,11,15
这个程序运行的结果和你原来那个是一样的。不信你自己运行一下。
请输入一个数字4
请输入一个数字5
请输入一个数字6
请输入一个数字0
0 6 11 15 请按任意键继续. . .
❽ 用c语言，利用递归函数求n!,由键盘输入任一整数，求n!
首先明确题目要求：递归函数，求n!
递归函数的含义：
编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。
n!表示阶乘函数，即1*2*3*……*n
下面给出代码：（C语言实现）
比较简单的尾递归实现：
#include<stdio.h>
longdigui(intn);//递归函数声明
intmain()
{
intn;
scanf("%d",&n);
printf("theresultis%ld",digui(n));//打印出递归值
return0;
}
longdigui(intn)//递归函数部分
{
if(n>1)
returnn*digui(n-1);//调用递归，让n与n-1相乘，直到n<1时
return1;//n<1时，返回1，实现n*(n-1)*(n-2)*……*3*2*1
}
❾ c语言中的递归
本人学c++，c的语法已经淡忘了，但是递归不管什么语言都是一个原理
其实简单一点来说就像数学里面的数列的通项公式：
例如一个数列是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)!,当n>1时,这样我们又有了递归形式，又可以以递归算法设计程序了。（楼上已给出谭老的程序，我就不写了）。
我给出一种优化的递归算法---尾递归。
从我给出的第一算法可以看出，先进栈再出栈，递归的效率是很低的。速度上完全比不上迭代（循环）。但是尾递归引入了一个新的函数参数，用这个新的函数参数来记录中间值.
普通递归阶乘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语言可以写出求n到m的累加的尾递归算法吗
#include<stdio.h>
intm,n;
intsum(intk)
{if(k==m)returnm;
returnk+sum(k-1);
}
intmain()
{scanf("%d%d",&m,&n);
printf("%d
",sum(n));
return0;
}