❶ 尾遞歸的實例
為了理解尾遞歸是如何工作的，讓我們再次以遞歸的形式計算階乘。首先，這可以很容易讓我們理解為什麼之前所定義的遞歸不是尾遞歸。回憶之前對計算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;
}