Ⅰ 遞歸調用底層堆棧原理是怎樣的
請問樓主懂匯編嗎？底層解釋離不開匯編
目前C語言的函數實現：
當需要調用一個函數的時候，代碼是需要從這里跳到其他地方（函數體）去執行的
這看上去似乎毫無疑問，但是當函數體執行完畢的時候，怎麼回到原來的地方去執行呢？
需要知道回到哪裡繼續執行，就需要在進入函數的時候先把要返回的地址保存起來
這個返回地址就是保存在棧（注意是棧，堆跟棧是有區別的）中的！
下面舉個例子
void f() f:
{
}
int main() 對應的部分匯編代碼可能是：
{
f(); call f
}
現在我們把匯編代碼對應的地址寫上去(假定代碼從內存0開始存放，每條指令長度都默認為1)
0 ; 函數f的首地址
1
2;ret
3 ;main的地址
4 ;call 0
5 ;ret
call 0 這個過程其實做了兩件事情：
push 5 ;call指令下一條指令的地址
jmp 0;跳到f()處執行函數體
ret 過程也做類似的事情
從棧頂彈出一個字（32位下為雙字）到(e)ip 然後去執行
有的時候，函數可能需要參數，這個時候參數也是被保存到棧中帶到函數體中去的
再解釋下去很復雜的，想知道 自己私m我吧
Ⅱ 遞歸文件夾堆棧溢出怎麼解決
解決不了的。
不用遞歸結構，才行。
遞歸，是一種華而不實的技巧。
編程時，難以估量堆棧的大小。
只有在實用時，才知道遞歸的次數。
所以，設計堆棧時，大了浪費，小了溢出。
因此，遞歸，不過是一種華而不實的技巧，而已。
Ⅲ Java JVM 中怎麼控制方法的遞歸調用。是在heap中的方法區，「重復」代碼段嗎
前面是我自己理解的後面是復制的
java有自動垃圾回收機制
當垃圾收集器判斷已經沒有任何引用指向對象的時候，會調用對象的finalize方法來釋放對象占據的內存空間~
java中垃圾回收以前聽老師講好像是內存滿了他才去做一次整體垃圾回收,在回收垃圾的同時會調用finalize方法.你在構造一個類時可以構造一個類時覆蓋他的finalize方法以便於該類在被垃圾回收時執行一些代碼,比如釋放資源.
1.JVM的gc概述
gc即垃圾收集機制是指jvm用於釋放那些不再使用的對象所佔用的內存。java語言並不要求jvm有gc，也沒有規定gc如何工作。不過常用的jvm都有gc，而且大多數gc都使用類似的演算法管理內存和執行收集操作。
在充分理解了垃圾收集演算法和執行過程後，才能有效的優化它的性能。有些垃圾收集專用於特殊的應用程序。比如，實時應用程序主要是為了避免垃圾收集中斷，而大多數OLTP應用程序則注重整體效率。理解了應用程序的工作負荷和jvm支持的垃圾收集演算法，便可以進行優化配置垃圾收集器。
垃圾收集的目的在於清除不再使用的對象。gc通過確定對象是否被活動對象引用來確定是否收集該對象。gc首先要判斷該對象是否是時候可以收集。兩種常用的方法是引用計數和對象引用遍歷。
1.1.引用計數
引用計數存儲對特定對象的所有引用數，也就是說，當應用程序創建引用以及引用超出范圍時，jvm必須適當增減引用數。當某對象的引用數為0時，便可以進行垃圾收集。
1.2.對象引用遍歷
早期的jvm使用引用計數，現在大多數jvm採用對象引用遍歷。對象引用遍歷從一組對象開始，沿著整個對象圖上的每條鏈接，遞歸確定可到達（reachable）的對象。如果某對象不能從這些根對象的一個（至少一個）到達，則將它作為垃圾收集。在對象遍歷階段，gc必須記住哪些對象可以到達，以便刪除不可到達的對象，這稱為標記（marking）對象。
下一步，gc要刪除不可到達的對象。刪除時，有些gc只是簡單的掃描堆棧，刪除未標記的未標記的對象，並釋放它們的內存以生成新的對象，這叫做清除（sweeping）。這種方法的問題在於內存會分成好多小段，而它們不足以用於新的對象，但是組合起來卻很大。因此，許多gc可以重新組織內存中的對象，並進行壓縮（compact），形成可利用的空間。
為此，gc需要停止其他的活動活動。這種方法意味著所有與應用程序相關的工作停止，只有gc運行。結果，在響應期間增減了許多混雜請求。另外，更復雜的 gc不斷增加或同時運行以減少或者清除應用程序的中斷。有的gc使用單線程完成這項工作，有的則採用多線程以增加效率。
2.幾種垃圾回收機制
2.1.標記－清除收集器
這種收集器首先遍歷對象圖並標記可到達的對象，然後掃描堆棧以尋找未標記對象並釋放它們的內存。這種收集器一般使用單線程工作並停止其他操作。
2.2.標記－壓縮收集器
有時也叫標記－清除－壓縮收集器，與標記－清除收集器有相同的標記階段。在第二階段，則把標記對象復制到堆棧的新域中以便壓縮堆棧。這種收集器也停止其他操作。
2.3.復制收集器
這種收集器將堆棧分為兩個域，常稱為半空間。每次僅使用一半的空間，jvm生成的新對象則放在另一半空間中。gc運行時，它把可到達對象復制到另一半空間，從而壓縮了堆棧。這種方法適用於短生存期的對象，持續復制長生存期的對象則導致效率降低。
2.4.增量收集器
增量收集器把堆棧分為多個域，每次僅從一個域收集垃圾。這會造成較小的應用程序中斷。
2.5.分代收集器
這種收集器把堆棧分為兩個或多個域，用以存放不同壽命的對象。jvm生成的新對象一般放在其中的某個域中。過一段時間，繼續存在的對象將獲得使用期並轉入更長壽命的域中。分代收集器對不同的域使用不同的演算法以優化性能。
2.6.並發收集器
並發收集器與應用程序同時運行。這些收集器在某點上（比如壓縮時）一般都不得不停止其他操作以完成特定的任務，但是因為其他應用程序可進行其他的後台操作，所以中斷其他處理的實際時間大大降低。
2.7.並行收集器
並行收集器使用某種傳統的演算法並使用多線程並行的執行它們的工作。在多cpu機器上使用多線程技術可以顯著的提高java應用程序的可擴展性。
3.Sun HotSpot
1.4.1 JVM堆大小的調整
Sun HotSpot 1.4.1使用分代收集器，它把堆分為三個主要的域：新域、舊域以及永久域。Jvm生成的所有新對象放在新域中。一旦對象經歷了一定數量的垃圾收集循環後，便獲得使用期並進入舊域。在永久域中jvm則存儲class和method對象。就配置而言，永久域是一個獨立域並且不認為是堆的一部分。
下面介紹如何控制這些域的大小。可使用-Xms和-Xmx 控制整個堆的原始大小或最大值。
下面的命令是把初始大小設置為128M：
java –Xms128m
–Xmx256m為控制新域的大小，可使用-XX:NewRatio設置新域在堆中所佔的比例。
下面的命令把整個堆設置成128m，新域比率設置成3，即新域與舊域比例為1：3，新域為堆的1/4或32M：
java –Xms128m –Xmx128m
–XX:NewRatio =3可使用-XX:NewSize和-XX:MaxNewsize設置新域的初始值和最大值。
下面的命令把新域的初始值和最大值設置成64m:
java –Xms256m –Xmx256m –Xmn64m
永久域默認大小為4m。運行程序時，jvm會調整永久域的大小以滿足需要。每次調整時，jvm會對堆進行一次完全的垃圾收集。
使用-XX:MaxPerSize標志來增加永久域搭大小。在WebLogic Server應用程序載入較多類時，經常需要增加永久域的最大值。當jvm載入類時，永久域中的對象急劇增加，從而使jvm不斷調整永久域大小。為了避免調整，可使用-XX:PerSize標志設置初始值。
下面把永久域初始值設置成32m，最大值設置成64m。
java -Xms512m -Xmx512m -Xmn128m -XX:PermSize=32m -XX:MaxPermSize=64m
默認狀態下，HotSpot在新域中使用復制收集器。該域一般分為三個部分。第一部分為Eden，用於生成新的對象。另兩部分稱為救助空間，當Eden 充滿時，收集器停止應用程序，把所有可到達對象復制到當前的from救助空間，一旦當前的from救助空間充滿，收集器則把可到達對象復制到當前的to救助空間。From和to救助空間互換角色。維持活動的對象將在救助空間不斷復制，直到它們獲得使用期並轉入舊域。使用-XX:SurvivorRatio 可控制新域子空間的大小。
同NewRation一樣，SurvivorRation規定某救助域與Eden空間的比值。比如，以下命令把新域設置成64m，Eden佔32m，每個救助域各佔16m：
java -Xms256m -Xmx256m -Xmn64m -XX:SurvivorRation =2
如前所述，默認狀態下HotSpot對新域使用復制收集器，對舊域使用標記－清除－壓縮收集器。在新域中使用復制收集器有很多意義，因為應用程序生成的大部分對象是短壽命的。理想狀態下，所有過渡對象在移出Eden空間時將被收集。如果能夠這樣的話，並且移出Eden空間的對象是長壽命的，那麼理論上可以立即把它們移進舊域，避免在救助空間反復復制。但是，應用程序不能適合這種理想狀態，因為它們有一小部分中長壽命的對象。最好是保持這些中長壽命的對象並放在新域中，因為復制小部分的對象總比壓縮舊域廉價。為控制新域中對象的復制，可用-XX:TargetSurvivorRatio控制救助空間的比例（該值是設置救助空間的使用比例。如救助空間位1M，該值50表示可用500K）。該值是一個百分比，默認值是50。當較大的堆棧使用較低的 sruvivorratio時，應增加該值到80至90，以更好利用救助空間。用-XX:maxtenuring threshold可控制上限。
為放置所有的復制全部發生以及希望對象從eden擴展到舊域，可以把MaxTenuring Threshold設置成0。設置完成後，實際上就不再使用救助空間了，因此應把SurvivorRatio設成最大值以最大化Eden空間，設置如下：
java … -XX:MaxTenuringThreshold=0 –XX:SurvivorRatio＝50000 …
4.BEA JRockit JVM的使用
Bea WebLogic 8.1使用的新的JVM用於Intel平台。在Bea安裝完畢的目錄下可以看到有一個類似於jrockit81sp1_141_03的文件夾。這就是 Bea新JVM所在目錄。不同於HotSpot把Java位元組碼編譯成本地碼，它預先編譯成類。JRockit還提供了更細致的功能用以觀察JVM的運行狀態，主要是獨立的GUI控制台（只能適用於使用Jrockit才能使用jrockit81sp1_141_03自帶的console監控一些cpu及 memory參數）或者WebLogic Server控制台。
Bea JRockit JVM支持4種垃圾收集器：
4.1.1.分代復制收集器
它與默認的分代收集器工作策略類似。對象在新域中分配，即JRockit文檔中的nursery。這種收集器最適合單cpu機上小型堆操作。
4.1.2.單空間並發收集器
該收集器使用完整堆，並與背景線程共同工作。盡管這種收集器可以消除中斷，但是收集器需花費較長的時間尋找死對象，而且處理應用程序時收集器經常運行。如果處理器不能應付應用程序產生的垃圾，它會中斷應用程序並關閉收集。
分代並發收集器這種收集器在護理域使用排它復制收集器，在舊域中則使用並發收集器。由於它比單空間共同發生收集器中斷頻繁，因此它需要較少的內存，應用程序的運行效率也較高，注意，過小的護理域可以導致大量的臨時對象被擴展到舊域中。這會造成收集器超負荷運作，甚至採用排它性工作方式完成收集。
4.1.3.並行收集器
該收集器也停止其他進程的工作，但使用多線程以加速收集進程。盡管它比其他的收集器易於引起長時間的中斷，但一般能更好的利用內存，程序效率也較高。
默認狀態下，JRockit使用分代並發收集器。要改變收集器，可使用-Xgc:，對應四個收集器分別為 gen，singlecon，gencon以及parallel。可使用-Xms和-Xmx設置堆的初始大小和最大值。要設置護理域，則使用- Xns:java –jrockit –Xms512m –Xmx512m –Xgc:gencon –Xns128m…盡管JRockit支持-verbose:gc開關，但它輸出的信息會因收集器的不同而異。JRockit還支持memory、 load和codegen的輸出。
注意 ：如果 使用JRockit JVM的話還可以使用WLS自帶的console（C:\bea\jrockit81sp1_141_03\bin下）來監控一些數據，如cpu， memery等。要想能構監控必須在啟動服務時startWeblogic.cmd中加入－Xmanagement參數。
5.如何從JVM中獲取信息來進行調整
-verbose.gc開關可顯示gc的操作內容。打開它，可以顯示最忙和最空閑收集行為發生的時間、收集前後的內存大小、收集需要的時間等。打開- xx:+ printgcdetails開關，可以詳細了解gc中的變化。打開-XX: + PrintGCTimeStamps開關，可以了解這些垃圾收集發生的時間，自jvm啟動以後以秒計量。最後，通過-xx: + PrintHeapAtGC開關了解堆的更詳細的信息。為了了解新域的情況，可以通過-XX:=PrintTenuringDistribution開關了解獲得使用期的對象權。
6.Pdm系統JVM調整
6.1.伺服器：前提內存1G 單CPU
可通過如下參數進行調整：－server 啟用伺服器模式（如果CPU多，伺服器機建議使用此項）
－Xms,－Xmx一般設為同樣大小。 800m
－Xmn 是將NewSize與MaxNewSize設為一致。320m
－XX:PerSize 64m
－XX:NewSize 320m 此值設大可調大新對象區，減少Full GC次數
－XX:MaxNewSize 320m
－XX:NewRato NewSize設了可不設。
－XX: SurvivorRatio
－XX:userParNewGC 可用來設置並行收集
－XX:ParallelGCThreads 可用來增加並行度
－XXUseParallelGC 設置後可以使用並行清除收集器
－XX：UseAdaptiveSizePolicy 與上面一個聯合使用效果更好，利用它可以自動優化新域大小以及救助空間比值
6.2.客戶機：通過在JNLP文件中設置參數來調整客戶端JVM
JNLP中參數：initial-heap-size和max-heap-size
這可以在framework的RequestManager中生成JNLP文件時加入上述參數，但是這些值是要求根據客戶機的硬體狀態變化的（如客戶機的內存大小等）。建議這兩個參數值設為客戶機可用內存的60％（有待測試）。為了在動態生成JNLP時以上兩個參數值能夠隨客戶機不同而不同，可靠慮獲得客戶機系統信息並將這些嵌到首頁index.jsp中作為連接請求的參數。
在設置了上述參數後可以通過Visualgc 來觀察垃圾回收的一些參數狀態，再做相應的調整來改善性能。一般的標準是減少fullgc的次數，最好硬體支持使用並行垃圾回收（要求多CPU）。
Ⅳ java 遞歸和內存的堆棧
基本數據類型就是在棧裡面開辟一塊空間，把裡面的值存進去。例如 : int i = 9; 就是開辟一塊內存，那塊內存的名字叫i，裡面的值存放的9; 引用數據類型也是在棧開辟一塊空間，當new 對象的時候就會在堆裡面開辟一塊空間，存儲這個對象的所有信息，然後棧的那塊空間裡面的值就會變成一系列內存地址，可以指向堆裡面的那塊內存。 例如: Date date; 這個就是在棧裡面開辟了塊內存，名字叫date，然後它裡面的值為null; date = new Date(); 然後這個就是在堆開辟了塊內存，把所有信息都放進去了，然後棧內存的date裡面的值就會變成指向堆內存的地址。 所以你調用date的時候就相當是在調用堆裡面的數據.
Ⅳ 有沒有辦法在遞歸函數裡面得到遞歸棧的內容
你自己查看調用堆棧就可以看堆棧裡面的內容吧。另外，你在遞歸函數裡面設斷點，一步步的堆棧調用你都可以看到的。還可以看當時的匯編代碼。
Ⅵ 下一個堆棧的地址保存在哪裡
堆棧中， 存儲的是相同類型的元素
所以每個元素大小相同
只需要知道棧頂指針就可以了
這個就是指向下一個元素的。
所以 下一個堆棧地址就是棧頂指針。
Ⅶ 怎樣用遞歸的方法遍歷棧
如何用棧實現遞歸與非遞歸的轉換
分類： C/C++2010-07-12 14:4012人閱讀評論(0)收藏舉報
如何用棧實現遞歸與非遞歸的轉換一.為什麼要學習遞歸與非遞歸的轉換的實現方法? 1)並不是每一門語言都支持遞歸的. 2)有助於理解遞歸的本質. 3)有助於理解棧,樹等數據結構.二.遞歸與非遞歸轉換的原理. 遞歸與非遞歸的轉換基於以下的原理:所有的遞歸程序都可以用樹結構表示出來.需要說明的是,這個"原理"並沒有經過嚴格的數學證明,只是我的一個猜想,不過在至少在我遇到的例子中是適用的. 學習過樹結構的人都知道,有三種方法可以遍歷樹:前序,中序,後序.理解這三種遍歷方式的遞歸和非遞歸的表達方式是能夠正確實現轉換的關鍵之處,所以我們先來談談這個.需要說明的是,這里以特殊的二叉樹來說明,不過大多數情況下二叉樹已經夠用,而且理解了二叉樹的遍歷,其它的樹遍歷方式就不難了. 1)前序遍歷 a)遞歸方式:
void preorder_recursive(Bitree T) /* 先序遍歷二叉樹的遞歸演算法 */
{
if (T) {
visit(T); /* 訪問當前結點 */
preorder_recursive(T->;lchild); /* 訪問左子樹 */
preorder_recursive(T->;rchild); /* 訪問右子樹 */
}
}
復制代碼
b)非遞歸方式
void preorder_nonrecursive(Bitree T) /* 先序遍歷二叉樹的非遞歸演算法 */
{
initstack(S);
push(S,T); /* 根指針進棧 */
while(!stackempty(S)) {
while(gettop(S,p)&&p) { /* 向左走到盡頭 */
visit(p); /* 每向前走一步都訪問當前結點 */
push(S,p->;lchild);
}
pop(S,p);
if(!stackempty(S)) { /* 向右走一步 */
pop(S,p);
push(S,p->;rchild);
}
}
}
復制代碼
2)中序遍歷 a)遞歸方式
void inorder_recursive(Bitree T) /* 中序遍歷二叉樹的遞歸演算法 */
{
if (T) {
inorder_recursive(T->;lchild); /* 訪問左子樹 */
visit(T); /* 訪問當前結點 */
inorder_recursive(T->;rchild); /* 訪問右子樹 */
}
}
復制代碼
b)非遞歸方式
void inorder_nonrecursive(Bitree T)
{
initstack(S); /* 初始化棧 */
push(S, T); /* 根指針入棧 */
while (!stackempty(S)) {
while (gettop(S, p) && p) /* 向左走到盡頭 */
push(S, p->;lchild);
pop(S, p); /* 空指針退棧 */
if (!stackempty(S)) {
pop(S, p);
visit(p); /* 訪問當前結點 */
push(S, p->;rchild); /* 向右走一步 */
}
}
}
復制代碼
3)後序遍歷 a)遞歸方式
void postorder_recursive(Bitree T) /* 中序遍歷二叉樹的遞歸演算法 */
{
if (T) {
postorder_recursive(T->;lchild); /* 訪問左子樹 */
postorder_recursive(T->;rchild); /* 訪問右子樹 */
visit(T); /* 訪問當前結點 */
}
}
復制代碼
b)非遞歸方式
typedef struct {
BTNode* ptr;
enum {0,1,2} mark;
} PMType; /* 有mark域的結點指針類型 */
void postorder_nonrecursive(BiTree T) /* 後續遍歷二叉樹的非遞歸演算法 */
{
PMType a;
initstack(S); /* S的元素為PMType類型 */
push (S,{T,0}); /* 根結點入棧 */
while(!stackempty(S)) {
pop(S,a);
switch(a.mark)
{
case 0:
push(S,{a.ptr,1}); /* 修改mark域 */
if(a.ptr->;lchild)
push(S,{a.ptr->;lchild,0}); /* 訪問左子樹 */
break;
case 1:
push(S,{a.ptr,2}); /* 修改mark域 */
if(a.ptr->;rchild)
push(S,{a.ptr->;rchild,0}); /* 訪問右子樹 */
break;
case 2:
visit(a.ptr); /* 訪問結點 */
}
}
}
復制代碼
4)如何實現遞歸與非遞歸的轉換 通常,一個函數在調用另一個函數之前,要作如下的事情:a)將實在參數,返回地址等信息傳遞 給被調用函數保存; b)為被調用函數的局部變數分配存儲區;c)將控制轉移到被調函數的入口. 從被調用函數返回調用函數之前,也要做三件事情:a)保存被調函數的計算結果;b)釋放被調 函數的數據區;c)依照被調函數保存的返回地址將控制轉移到調用函數. 所有的這些,不論是變數還是地址,本質上來說都是"數據",都是保存在系統所分配的棧中的. ok,到這里已經解決了第一個問題:遞歸調用時數據都是保存在棧中的,有多少個數據需要保存 就要設置多少個棧,而且最重要的一點是:控制所有這些棧的棧頂指針都是相同的,否則無法實現 同步. 下面來解決第二個問題:在非遞歸中,程序如何知道到底要轉移到哪個部分繼續執行?回到上 面說的樹的三種遍歷方式,抽象出來只有三種操作:訪問當前結點,訪問左子樹,訪問右子樹.這三 種操作的順序不同,遍歷方式也不同.如果我們再抽象一點,對這三種操作再進行一個概括,可以 得到:a)訪問當前結點:對目前的數據進行一些處理;b)訪問左子樹:變換當前的數據以進行下一次 處理;c)訪問右子樹:再次變換當前的數據以進行下一次處理(與訪問左子樹所不同的方式). 下面以先序遍歷來說明:
void preorder_recursive(Bitree T) /* 先序遍歷二叉樹的遞歸演算法 */
{
if (T) {
visit(T); /* 訪問當前結點 */
preorder_recursive(T->;lchild); /* 訪問左子樹 */
preorder_recursive(T->;rchild); /* 訪問右子樹 */
}
}
復制代碼
visit(T)這個操作就是對當前數據進行的處理, preorder_recursive(T->;lchild)就是把當前 數據變換為它的左子樹,訪問右子樹的操作可以同樣理解了. 現在回到我們提出的第二個問題:如何確定轉移到哪裡繼續執行?關鍵在於一下三個地方:a) 確定對當前數據的訪問順序,簡單一點說就是確定這個遞歸程序可以轉換為哪種方式遍歷的樹結 構;b)確定這個遞歸函數轉換為遞歸調用樹時的分支是如何劃分的,即確定什麼是這個遞歸調用 樹的"左子樹"和"右子樹"c)確定這個遞歸調用樹何時返回,即確定什麼結點是這個遞歸調用樹的 "葉子結點". 三.三個例子 好了上面的理論知識已經足夠了,下面讓我們看看幾個例子,結合例子加深我們對問題的認識 .即使上面的理論你沒有完全明白,不要氣餒,對事物的認識總是曲折的,多看多想你一定可以明 白(事實上我也是花了兩個星期的時間才弄得比較明白得). 1)例子一:
f(n) = n + 1; (n <2)
f[n/2] + f[n/4](n >;= 2);
這個例子相對簡單一些,遞歸程序如下:
int f_recursive(int n)
{
int u1, u2, f;
if (n < 2)
f = n + 1;
else {
u1 = f_recursive((int)(n/2));
u2 = f_recursive((int)(n/4));
f = u1 * u2;
}
return f;
}
復制代碼
下面按照我們上面說的,確定好遞歸調用樹的結構,這一步是最重要的.首先,什麼是葉子結點 ,我們看到當n < 2時f = n + 1,這就是返回的語句,有人問為什麼不是f = u1 * u2,這也是一個 返回的語句呀?答案是:這條語句是在u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))之後 執行的,是這兩條語句的父結點. 其次,什麼是當前結點,由上面的分析,f = u1 * u2即是父結點 .然後,順理成章的u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))就分別是左子樹和右子 樹了.最後,我們可以看到,這個遞歸函數可以表示成後序遍歷的二叉調用樹.好了,樹的情況分析 到這里,下面來分析一下棧的情況,看看我們要把什麼數據保存在棧中,在上面給出的後序遍歷的如果這個過程你沒 非遞歸程序中我們已經看到了要加入一個標志域,因此在棧中要保存這個標志域;另外,u1,u2和 每次調用遞歸函數時的n/2和n/4參數都要保存,這樣就要分別有三個棧分別保存:標志域,返回量 和參數,不過我們可以做一個優化,因為在向上一層返回的時候,參數已經沒有用了,而返回量也 只有在向上返回時才用到,因此可以把這兩個棧合為一個棧.如果對於上面的分析你沒有明白,建 議你根據這個遞歸函數寫出它的遞歸棧的變化情況以加深理解,再次重申一點:前期對樹結構和 棧的分析是最重要的,如果你的程序出錯,那麼請返回到這一步來再次分析,最好把遞歸調用樹和 棧的變化情況都畫出來,並且結合一些簡單的參數來人工分析你的演算法到底出錯在哪裡. ok,下面給出我花了兩天功夫想出來的非遞歸程序(再次提醒你不要氣餒,大家都是這么過來 的).
int f_nonrecursive(int n)
{
int stack[20], flag[20], cp;
/* 初始化棧和棧頂指針 */
cp = 0;
stack[0] = n;
flag[0] = 0;
while (cp >;= 0) {
switch(flag[cp]) {
case 0: /* 訪問的是根結點 */
if (stack[cp] >;= 2) { /* 左子樹入棧 */
flag[cp] = 1; /* 修改標志域 */
cp++;
stack[cp] = (int)(stack[cp - 1] / 2);
flag[cp] = 0;
} else { /* 否則為葉子結點 */
stack[cp] += 1;
flag[cp] = 2;
}
break;
case 1: /* 訪問的是左子樹 */
if (stack[cp] >;= 2) { /* 右子樹入棧 */
flag[cp] = 2; /* 修改標志域 */
cp += 2;
stack[cp] = (int)(stack[cp - 2] / 4);
flag[cp] = 1;
} else { /* 否則為葉子結點 */
stack[cp] += 1;
flag[cp] = 2;
}
break;
case 2: /* */
if (flag[cp - 1] == 2) { /* 當前是右子樹嗎? */
/*
* 如果是右子樹, 那麼對某一棵子樹的後序遍歷已經
* 結束,接下來就是對這棵子樹的根結點的訪問
*/
stack[cp - 2] = stack[cp] * stack[cp - 1];
flag[cp - 2] = 2;
cp = cp - 2;
} else
/* 否則退回到後序遍歷的上一個結點 */
cp--;
break;
}
}
return stack[0];
}
復制代碼
演算法分析:a)flag只有三個可能值:0表示第一次訪問該結點,1表示訪問的是左子樹,2表示 已經結束了對某一棵子樹的訪問,可能當前結點是這棵子樹的右子樹,也可能是葉子結點.b)每 遍歷到某個結點的時候,如果這個結點滿足葉子結點的條件,那麼把它的flag域設為2;否則根據 訪問的是根結點,左子樹或是右子樹來設置flag域,以便決定下一次訪問該節點時的程序轉向. 2)例子二 快速排序演算法 遞歸演算法如下:
void swap(int array[], int low, int high)
{
int temp;
temp = array[low];
array[low] = array[high];
array[high] = temp;
}
int partition(int array[], int low, int high)
{
int p;
p = array[low];
while (low < high) {
while (low < high && array[high] >;= p)
high--;
swap(array,low,high);
while (low < high && array[low] <= p)
low++;
swap(array,low,high);
}
return low;
}
void qsort_recursive(int array[], int low, int high)
{
int p;
if(low < high) {
p = partition(array, low, high);
qsort_recursive(array, low, p - 1);
qsort_recursive(array, p + 1, high);
}
}
復制代碼
需要說明一下快速排序的演算法: partition函數根據數組中的某一個數把數組劃分為兩個部分, 左邊的部分均不大於這個數,右邊的數均不小於這個數,然後再對左右兩邊的數組再進行劃分.這 里我們專注於遞歸與非遞歸的轉換,partition函數在非遞歸函數中同樣的可以調用(其實 partition函數就是對當前結點的訪問). 再次進行遞歸調用樹和棧的分析: 遞歸調用樹:a)對當前結點的訪問是調用partition函數;b)左子樹: qsort_recursive(array, low, p - 1);c)右子樹:qsort_recursive(array, p + 1, high); d)葉子結點:當low < high時;e)可以看出這是一個先序調用的二叉樹 棧:要保存的數據是兩個表示範圍的坐標.
void qsort_nonrecursive(int array[], int low, int high)
{
int m[50], n[50], cp, p;
/* 初始化棧和棧頂指針 */
cp = 0;
m[0] = low;
n[0] = high;
while (m[cp] < n[cp]) {
while (m[cp] < n[cp]) { /* 向左走到盡頭 */
p = partition(array, m[cp], n[cp]); /* 對當前結點的訪問 */
cp++;
m[cp] = m[cp - 1];
n[cp] = p - 1;
}
/* 向右走一步 */
m[cp + 1] = n[cp] + 2;
n[cp + 1] = n[cp - 1];
cp++;
}
}
復制代碼
3)例子三 阿克曼函數:
akm(m, n) = n + 1; (m = 0時)
akm(m - 1, 1); (n = 0時)
akm(m - 1, akm(m, n - 1)); (m != 0且n != 0時)
復制代碼
遞歸演算法如下:
int akm_recursive(int m, int n)
{
int temp;
if (m == 0)
return (n + 1);
else if (n == 0)
return akm_recursive(m - 1, 1);
else {
temp = akm_recursive(m, n - 1);
return akm_recursive(m - 1, temp);
}
}
Ⅷ 遞歸演算法和棧有什麼關系棧又是怎樣運用的
遞歸演算法和棧都有後進先出這個性質，基本上能用遞歸完成的演算法都可以用棧完成，都是運用後進先出這個性質的
用棧之前首先你要想明白你需要使用「後進先出」干什麼，然後才可編寫演算法，使用中往往是先把數據都壓入棧中，然後使用使取出便可，
像表達式求解就是典型的運用棧的例子，可以去看看，會對棧的理解印象深刻些
# include <stdio.h>
# define origial 100
# define add 10
typedef struct
{
int *base;
int *top;
int stack;
}opno;
typedef struct
{
char *base;
char *top;
int stack;
}optr;
void initstacka(opno *a)
{
a->base=(int *)malloc(sizeof(int)*origial);
a->top=a->base;
a->stack=origial;
}
void initstackb(optr *b)
{
b->base=(char *)malloc(sizeof(char)*origial);
b->top=b->base;
b->stack=origial;
*b->top++='#';
}
void pusha(opno *a,int b)
{
if(a->top-a->base>=a->stack)
{
a->base=(int *)realloc(a->base,sizeof(int)*(a->stack+add));
a->top=a->base+a->stack;
a->stack+=add;
}
*a->top++=b;
}
void pushb(optr *b,char c)
{
if(b->top-b->base>=b->stack)
{
b->base=(char *)realloc(b->base,sizeof(char)*(b->stack+add));
b->top=b->base+b->stack;
b->stack+=add;
}
*b->top++=c;
}
int determine(char c)
{
if(c>='0'&&c<='9')
return(1);
else
return(0);
}
char gettopb(optr *b)
{
char a;
a=*(b->top-1);
return(a);
}
char shuzu(int i,int j)
{
char a[7][7]={{'>','>','<','<','<','>','>'},{'>','>','<','<','<','>','>'},{'>','>','>','>','<','>','>'},{'>','>','>','>','<','>','>'},{'<','<','<','<','<','=','0'},{'>','>','>','>','0','>','>'},{'<','<','<','<','<','0','='}};
return(a[i][j]);
}
char precede(char b,char a)
{
int i,j;
char s;
switch(b)
{
case '+':i=0;
break;
case '-':i=1;
break;
case '*':i=2;
break;
case '/':i=3;
break;
case '(':i=4;
break;
case ')':i=5;
break;
case '#':i=6;
break;
}
switch(a)
{
case '+':j=0;
break;
case '-':j=1;
break;
case '*':j=2;
break;
case '/':j=3;
break;
case '(':j=4;
break;
case ')':j=5;
break;
case '#':j=6;
break;
}
s=shuzu(i,j);
return(s);
}
void popb(optr *a,char *b)
{
*b=*--a->top;
}
void popa(opno *a,int *b)
{
*b=*--a->top;
}
int count(int a,int b,char c)
{
int sum=0;
switch(c)
{
case '+':sum=a+b;
break;
case '-':sum=a-b;
break;
case '*':sum=a*b;
break;
case '/':sum=a/b;
break;
}
return(sum);
}
int empty(optr *a)
{
if(a->top==a->base)
return(1);
else
return(0);
}
void main()
{
opno *a;
optr *b;
char c;
char d[50];
int i=0,j=0,k,sum=0,p,o,r,w;
int y[3];
a=(opno *)malloc(sizeof(opno));
b=(optr *)malloc(sizeof(optr));
initstacka(a);
initstackb(b);
printf("請輸入表達式！\n");
scanf("%s",d);
while(d[i]!='#'&&d[i]!='\0')
if(determine(d[i]))
{
sum=0;
y[j]=d[i]-'0';
while(determine(d[i+1]))
{
i=i+1;
y[++j]=d[i]-'0';
}
for(k=0;k<=j;k++)
sum=sum*10+y[k];
if(sum!=0)
pusha(a,sum);
else
pusha(a,y[0]);
j=0;
for(k=0;k<3;k++)
y[k]=0;
i=i+1;
}
else
{
switch(precede(gettopb(b),d[i]))
{
case '>':popb(b,&c);
popa(a,&p);
popa(a,&o);
r=count(o,p,c);
pusha(a,r);
break;
case '=':popb(b,&c);
i++;
break;
case '<':pushb(b,d[i]);
i++;
break;
}
}
popb(b,&c);
while(c!='#')
{
popa(a,&o);
popa(a,&p);
r=count(o,p,c);
pusha(a,r);
popb(b,&c);
}
popa(a,&w);
printf("%d",w);
}
這就是運用棧寫得表達式求值
Ⅸ 在單片機PUSH指令如何使用的，是怎樣把數據保存在堆棧區的。又是如何恢復的
PUSH A 錯，如果是PUSH ACC就對了
PUSH B 對
PUSH PSW 對
PUSH R0 錯
51單片機中，所有SFR寄存器可以用名稱入棧，通用寄存器只能用直接定址
Ⅹ 遞歸調用時,棧中保存的是函數的返回值嗎
一般是，函數執行到那一步的地址、這一次函數執行時的參數變數，遞歸觸底後、逐級返回時壓入返回值到調用該次函數的函數地址參數變數堆棧上。說的可能不好理解，但是遞歸描述就是很麻煩，希望有高手給個簡單明了的描述。