數據結構的遞歸什麼意思

① 遞歸的重要組成

在計算機編程語言，一個遞歸類型（也被稱為遞歸定義，電感定義或感應數據類型）是一種數據類型，選擇那些包含相同類型的其它值的值。遞歸類型的數據通常被視為有向圖。

遞歸在計算機科學中的一個重要應用是定義動態數據結構，如列表和樹。遞歸數據結構可以響應運行時要求動態增長到任意大的大小; 相反，必須在編譯時設置靜態數組的大小要求。

② 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。

③ 誰給解釋一下，數據結構中的遞歸是什麼意思

遞歸：
遞歸是一種重要的編程技術。該方法用於讓一個函數從其內部調用其自身。一個示例就是計算階乘。0 的階乘被特別地定義為 1。 更大數的階乘是通過計算 1 * 2 * ...來求得的。

④ 在數據結構的演算法中,1什麼是遞歸,2如何設計遞歸演算法

一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。給你一個示例做1+2+3+。。。+n
int digui(int n)
{ int t;
if(n>1)
{t=digui(n-1)+n;
return t;}
else
return 1;
}

⑤ 數據結構與演算法(8)-棧與遞歸的關系

數據結構與演算法(7)-棧

遞歸： 在數學與計算機科學中，是指在函數的定義中使用函數自身的方法。也就是說，遞歸演算法是一種直接或者間接調用自身函數或者方法的演算法。 通俗來說，遞歸演算法的實質是把問題分解成規模縮小的同類問題的子問題，然後遞歸調用方法來表示問題的解。

比如很多數學定義是遞歸的，比如階乘、斐波那契數列，盧卡斯數列等。對於類似的復雜問題，若能拆分為幾個簡單的相同或類似的子問題來求解，便稱為遞歸求解。

其數據結構本身具有遞歸的特性，例如鏈表，通過指針指向下一個節點，所以在節點中包含了自身。
示例：(列印鏈表內的所有元素)

在遞歸演算法中，如果當遞歸結束條件成立只執行return操作時，分治法求解遞歸問題演算法一般形式可以簡化為：

有些問題雖然本身沒有明顯的遞歸結構，但是采樣遞歸求解比迭代求解更簡單，比如漢諾塔問題，皇後問題，迷宮問題

一個遞歸函數在其執行過程中，需要多次進行自我調用，那麼遞歸函數是如何執行的呢？
函數調用： 在高級語言的程序中，函數的調用都是通過棧來進行的。通常在一個函數的運行期間調用另一個函數時，在運行被調用函數之前系統一般需要完成3件事情：

從被調用函數返回需要調用函數之前，系統同樣需要完成3件事

當多個函數構成嵌套調用時，按照先調用後返回的原則，上述函數之間的信息傳遞和控制轉移則需要通過棧來實現，即系統將整個程序運行時所需要的數據空間都安排在一個棧中，每當調用一個函數的時候，就在它的棧頂分配一個存儲區域，每當這個函數退出時，就釋放它的存儲區域，從而回到調用函數棧區的棧頂。
示例：

通過匯編看函數調用棧：

一個遞歸函數的運行過程類似多個函數的嵌套調用，只是調用函數和被調用函數是同一個函數，因此和每次調用相關的一個重要概念是遞歸函數運行的運行「層次」，假設調用該遞歸函數的主函數為第0層，則從主函數調用遞歸函數進入第1層，以後每調用一次就加一層，每返回一層就減一層，直至返回到主函數。

為了保證遞歸函數正確執行，系統需要設立一個「遞歸工作棧」作為整個遞歸函數運行期間使用的數據存儲區，每一層遞歸所需信息構成一個工作記錄，其中包括所有的實參，所有的局部變數，以及上一層的返回地址，每進入一層遞歸就產生一個新的工作記錄壓入棧頂，每退出一個遞歸就從棧頂彈出一個工作記錄，則當前執行層的工作記錄稱為「活動記錄」。

本質上講呢，在計算機中，函數調用是通過棧（stack）這種數據結構實現的，每當進入一個函數調用，棧就會加一層棧幀，每當函數返回，棧就會減一層棧幀。由於棧的大小不是無限的，所以遞歸調用的次數過多，佔用內存就越多，就會導致棧溢出。

漢諾塔 ：漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根 金剛石 柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

假設柱子編號分別為A、B、C，盤子的個數為n，我們要做的是將A上的所有盤子按照規則移動到C柱上，B柱作為輔助柱。計算移動次數。

⑥ C語言中的遞歸是什麼意思

遞歸就是 函數自己調用自己 ..
第一個是主函數 ..
第二個cj()函數才是一個遞歸函數 ..
在cj()函數體裡面 有cj(n--)這個語句 就是它再次調用自己 只不過參數變化了 ..

⑦ 數據結構之遞歸一

上一篇寫了關於數學歸納法的一些概念，那麼這一篇就該帶大家去體會一下遞歸了。

這一篇主要通過一個小游戲帶領大家走入遞歸的世界，這個游戲叫做 漢諾塔 ，先說下游戲規則，如下圖所示，有三根柱子，我們需要把套在 A 柱子上的圓環全部移動到 B 上，一次只能移動一個圓環，當然圓環的順序也得一樣。那麼 C 柱則起到了中轉的作用。

下面是最終需要達到的結果

有點人可能會說，一開始就讓我們接觸這么多的圓環，怎麼也會搞混啊，那麼我們就先從簡單一點的開始吧。先從只有三個的圓環入手。

這里我們需要把 A 上的三個圓環藉助 C 全部移動到 B 柱上。首先開始之前我們應該思考下，要想把三個全部移動到 B 柱上，則先需要把上面兩個拿到 C 柱，然後把最大的那個拿到 B 柱，最後把上面的兩個放到最大的上面。當我們把兩個環拿到 C 的時候，勢必需要藉助 B 柱作為一個臨時中轉，這樣我們就完成了移動的過程。寫成規范一點的步驟就是：

步驟一： 把兩個環從 A 柱經過 B 柱進行中轉移動到 C 柱。

步驟二： 把第三個環拿到 B 柱。

步驟三： 把兩個環從 C 柱經過 A 柱進行中轉移動到 B 柱。

經過這三個步驟我們就實現了三個圓環的移動。這時候我們就可以結合上一篇講過的數學歸納法進行遞推到如果有 n 個圓環怎麼移動的問題了。

首先，如果 n = 0 ，不做任何移動。

其次，如果 n > 0 ，做三個步驟：

步驟一： 把 n - 1 個環從 A 柱經過 B 柱進行中轉移動到 C 柱。

步驟二： 把第 n 個環拿到 B 柱。

步驟三： 把 n - 1 個環從 C 柱經過 A 柱進行中轉移動到 B 柱。

至於如何把 n - 1 個圓環移動，上面通過兩個環的例子已經給大家進行了簡單的說明，這就是遞歸和數學歸納法的不同之處了，數學歸納法是先知道簡單的怎麼做去推導出一般的結論，而遞歸則是知道一般的要求，通過把一般的問題化成簡單的問題來解決。如果大家光聽理論有些混亂的話，可以去玩玩漢諾塔的小游戲體會下

當然最後我們得從程序員的角度去實現一下漢諾塔的解法

我們可以通過游戲對程序的結果進行驗證，在下一篇中會對這個游戲有個簡短的總結。

這一篇通過一個小游戲帶大家粗略了解了遞歸的概念，後面還將有兩個例子和一個總結對遞歸進行了解。

⑧ 數據結構中的二叉樹中的遞歸怎麼理解

數據結構中的二叉樹中的遞歸理解如下：

具體實現代碼

1 function preorder(node){

2 if(!!node){//轉換為布爾值

3 divlist.push(node);

4 preorder(node.firstElementChild);

5 preorder(node.lastElementChild);

6 }

7 }

對代碼的幾點說明：

divlist為一個數組，是一個全局變數，存儲最終遍歷結果。可能有的同學不熟悉JavaScript，node.firstElementChild與node.lastElementChild分別指父節點的第一個元素節點和最後一個元素節點，即對應父節點的左孩子和右孩子。

二叉樹是以DOM樹的形式模擬

所謂遞歸可以分為兩部分來理解：「遞」和「歸」。

「遞」指按照代碼執行順序執行，這個和我們正常的思維一致不難理解。但有一點需要注意的是，在「遞」的同時會把節點按照訪問的順序逐次壓入到一個堆棧中。

「歸」是指「遞」進行到盡頭時，開始根據「遞」的過程中形成的堆棧進行出棧，最終得到結果。

對於二叉樹的先序遍歷，可以看出包含了兩個對自己的調用，及包含兩個遍歷。

我們首先傳進去的node是1，根據程序執行過程，我們可以知道在執行到一個階段的盡頭時，將會形成這樣一個堆棧

由於左子樹已經到了盡頭，所以第一個遍歷暫告一段落。按照代碼執行的順序，接下來需要執行preorder(node.lastElementChild);也就是右子樹的遍歷，因為4依然沒有右孩子，所以按照出棧的順序依次遍歷2和1的右子樹。為了說明簡單，再次貼一下代碼

1 function preorder(node){

2 if(!!node){//轉換為布爾值

3 divlist.push(node);

4 preorder(node.firstElementChild);

5 preorder(node.lastElementChild);

6 }

7 }

再來具體分析一下遍歷2的右孩子時的過程。

當把2的節點傳給preorder函數時，只執行了preorder(node.firstElementChild);，preorder(node.lastElementChild);還沒有執行，按照程序執行順序此時需要執行。

具體的執行步驟如下：

此時堆棧內又依次被壓入了5，6，7三個元素節點

總結

遞歸也沒有那麼可怕，該執行的代碼還是會執行，不過順序可能和我們平常的思維不一致。它會不斷的調用自身直到一個停止條件的滿足，然後再回溯會第一個節點。

⑨ 遞歸方法的定義

1、定義是遞歸的：

（1）n!的遞歸實現：

遞歸方法：

public class Method { int fun(int n){ if(n==1) return 1; else
return(fun(n-1)*n);
}
}
public class RecursionDemo { public static void main (String[] args){
Method m=new Method(); int num=m.fun(3);
System.out.println(num);
}
}

遞歸方法分析：

（1）該方法是直接遞歸，即自己調用自己。

例如：在執行fun(3)的時候，先執行fun（2）*3，而fun（2）=fun（1）*2，fun（1）=1。

（2）遞歸過程將問題的規模逐步縮小，參數的大小每次減1。一個個重復的過程，通過調用自身，減少了代碼量。

（3）因為遞歸調用語句是在最後一句，因此，這種遞歸方式也稱為尾遞歸。

2、數據結構是遞歸的：

單鏈表的存儲結構定義。

3、問題的求解是遞歸的：

#include<stdio.h> #include<malloc.h> #include<stdlib.h>#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10#define OVERFLOW -2#define ERROR 0
#define OK 1typedef int ElemType;

typedef struct{ //存儲結構 ElemType *elem; //指針類型 int length;
int listsize;
}SqList;//順序表的結構類型 typedef int Status;

Status InitList(SqList &L){
L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//動態分配存儲空間 if(!L.elem) exit(OVERFLOW); //分配失敗退出 L.length=0; //空表 L.listsize=LIST_INIT_SIZE; //初始存儲容量 return OK;
}

Status ListInsert(SqList &L,int i,ElemType e){//在第 i 個元素前插入一個新的元素e if(i<1 || i > L.length+1) return ERROR; //i值不合法 if(L.length>=L.listsize) //存儲空間不足 {
ElemType * newbase=(ElemType *)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) exit(OVERFLOW); //分配失敗 L.elem=newbase;
L.listsize=LIST_INIT_SIZE+LISTINCREMENT;
}
for (int j=L.length; j>=i; --j)
L.elem[j]=L.elem[j-1];
L.elem[i-1]=e;
L.length++;return OK;
}

Status ListEmpty(SqList L){ //判斷順序表是否為空return L.length == 0;
}

Status ListPrint(SqList &L) {
printf(" 順序表為： ");
if (ListEmpty(L)) {
printf(" 空。 ");
return ERROR;
}
for (int i=0; i<L.length; ++i)
{
printf("%-4d ", L.elem[i]);
}
printf(" ");
return OK;
}int Sum(SqList L,int i){ if(i==L.length) return 0; else
return(L.elem[i]+Sum(L,i+1));
}

main(){

SqList L;
ElemType e;
int i,j;
InitList(L);


printf(" 請輸入你想創建的順序表中元素的個數： ");
scanf("%d",&i);
if(i<1) printf(" 您輸入的值有誤，無法創建順序表。 ");
else {
printf(" 請您依次輸入您想創建的順序表的元素： ");
for(j=1;j<=i;j++)
{
scanf("%d",&e);
ListInsert(L,L.length+1,e); //尾插 }
}
ListPrint(L); //遍歷順序表 int result=Sum(L,0);
printf( "順序表所有元素的和為：%d",result);
}

這個程序是求解順序表的元素的和，從順序表的第一個元素開始，依次向後查找元素，並進行求和運算。

⑩ 數據結構中的二叉樹中的遞歸怎麼理解

//遞歸方法實現創建
status createbitree(bitree *t)
{
int ch=0;
cin>>ch;
if(ch==0)(*t)=NULL;
else
{
(*t)=(bitree)malloc(sizeof(binode));
(*t)->data=ch;
createbitree(&(*t)->lchild);
createbitree(&(*t)->rchild);
}
return OK;
}
這是個按條件先序遍歷的順序輸入的二叉樹，你必須理解的是這些代碼中的遞歸有一個隱含的條件就是利用棧來進行存儲，有一個壓棧和出棧的過程，棧起了一個保護現場的作用，左孩子是優先的，一直到這個結點為空，才進行彈棧將這個結點的父親結點，並且進入這個父親結點的右孩子，對這個過程重復。
有什麼問題可以繼續找我，數據結構我學的還可以的