在遞歸演算法中

① 在遞歸演算法執行過程中,計算機系統必定會用到的數據

指針 因為遞歸調用必然會用到函數指針對同一函數體進行反復的調用。在遞歸演算法執行過程中,計算機系統必定會用到的數據

② 六、遞歸與回溯演算法

在計算機領域裡面，很多問題都可以要採用遞歸演算法來解決。遞歸中，最長用到的方法就是回溯法。我們具體分析問題的時候，可以發現這類問題本質是一個樹的形狀。

遞歸演算法的本質還是將原來的問題轉化為了更小的同一問題，進行解決。一般注意兩點：
1、遞歸終止的條件。對應到了遞歸演算法中最基本的問題，也是最最簡單的問題。
2、遞歸過程。遞歸過程需要將原問題一步一步的推到更小的 同一 問題，更小的意思就是子問題解決起來就更加的簡單。有寫情況是能夠找到一個遞推的公式的。這個過程中就需要透徹的去理解遞歸函數的意義。明確這個函數的輸入和輸出是什麼，這樣來寫的話，就清晰多了。

因為有了這樣的遞歸公式，那麼我們就很容易的能看出來遞歸的終止條件就是我們知道的f(0)和f(1)了。有了f(0)和f(1)之後，我們就能夠繼續的遞推出f(3)一直到f(n)了。

但是我們現在才用一個遞歸演算法的思想來解決這個問題:

像我們常見的數據結構如鏈表、樹、圖等都是有著天然的遞歸結構的，鏈表由於是一個線性的結構，那麼通常我們也是能夠直接循環遍歷就能解決問題的，但是這里我們用遞歸法來解決一下LeetCode上面的問題
LeetCode 203 移除鏈表元素
分析：鏈表的結構可以理解成一個節點連接這一個更短的鏈表，這樣依次一直看下去，直到最後一個節點None，那麼我們這個時候的遞歸終止條件就是head指向None了，返回的就是None

深入的理解遞歸演算法之後，我們就開始進行回溯法的學習。通過LeetCode上面的幾道題，我們來深入的探討一下遞歸與回溯法的應用。

持續更新中...
數據結構與演算法系列博客：
一、數據結構與演算法概述
二、數組及LeetCode典型題目分析
三、鏈表（Linked list）以及LeetCode題
四、棧與隊列（Stack and Queue
五、樹（Trees）
六、遞歸與回溯演算法
七、動態規劃
八、排序與搜索
九、哈希表

參考資料
1、
2、
3、

③ 什麼是遞歸演算法

遞歸演算法就是一個函數通過不斷對自己的調用而求得最終結果的一種思維巧妙但是開銷很大的演算法。
比如：
漢諾塔的遞歸演算法：
void move(char x,char y){
printf("%c-->%c\n",x,y);
}

void hanoi(int n,char one,char two,char three){
/*將n個盤從one座藉助two座，移到three座*/
if(n==1) move(one,three);
else{
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}

main(){
int n;
printf("input the number of diskes:");
scanf("%d",&n);
printf("The step to moving %3d diskes:\n",n);
hanoi(n,'A','B','C');
}
我說下遞歸的理解方法
首先：對於遞歸這一類函數，你不要糾結於他是干什麼的，只要知道他的一個模糊功能是什麼就行，等於把他想像成一個能實現某項功能的黑盒子，而不去管它的內部操作先，好，我們來看下漢諾塔是怎麼樣解決的
首先按我上面說的把遞歸函數想像成某個功能的黑盒子，void hanoi(int n,char one,char two,char three); 這個遞歸函數的功能是：能將n個由小到大放置的小長方形從one 位置，經過two位置 移動到three位置。那麼你的主程序要解決的問題是要將m個的"漢諾塊"由A藉助B移動到C，根據我們上面說的漢諾塔的功能，我相信傻子也知道在主函數中寫道：hanoi(m,A,B,C)就能實現將m個塊由A藉助B碼放到C，對吧？所以，mian函數裡面有hanoi(m,'A','C','B');這個調用。
接下來我們看看要實現hannoi的這個功能，hannoi函數應該幹些什麼？
在hannoi函數里有這么三行
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
同樣以黑盒子的思想看待他，要想把n個塊由A經過B搬到C去，是不是可以分為上面三步呢？
這三部是：第一步將除了最後最長的那一塊以外的n-1塊由one位置經由three搬到two 也就是從A由C搬到B 然後把最下面最長那一塊用move函數把他從A直接搬到C 完事後 第三步再次將剛剛的n-1塊藉助hannoi函數的功能從B由A搬回到C 這樣的三步實習了n塊由A經過B到C這樣一個功能，同樣你不用糾結於hanoi函數到底如何實現這個功能的，只要知道他有這么一個神奇的功能就行
最後：遞歸都有收尾的時候對吧，收尾就是當只有一塊的時候漢諾塔怎麼個玩法呢？很簡單吧，直接把那一塊有Amove到C我們就完成了，所以hanoni這個函數最後還要加上 if(n==1)move(one,three);（當只有一塊時，直接有Amove到C位置就行）這么一個條件就能實現hanoin函數n>=1時將n個塊由A經由B搬到C的完整功能了。
遞歸這個復雜的思想就是這樣簡單解決的，呵呵 不知道你看懂沒？純手打，希望能幫你理解遞歸
總結起來就是不要管遞歸的具體實現細節步驟，只要知道他的功能是什麼，然後利用他自己的功能通過調用他自己去解決自己的功能（好繞口啊，日）最後加上一個極限情況的條件即可，比如上面說的1個的情況。

④ 遞歸演算法

遞歸演算法
遞歸演算法流程
遞歸過程一般通過函數或子過程來實現。遞歸演算法：在函數或子過程的內部，直接或者間接地調用自己的演算法。
遞歸演算法的特點
遞歸演算法是一種直接或者間接地調用自身的演算法。在計算機編寫程序中，遞歸演算法對解決一大類問題是十分有效的，它往往使演算法的描述簡潔而且易於理解。 遞歸演算法解決問題的特點： (1) 遞歸就是在過程或函數里調用自身。 (2) 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。 (3) 遞歸演算法解題通常顯得很簡潔，但遞歸演算法解題的運行效率較低。所以一般不提倡用遞歸演算法設計程序。 (4) 在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。所以一般不提倡用遞歸演算法設計程序。
遞歸演算法要求
遞歸演算法所體現的「重復」一般有三個要求： 一是每次調用在規模上都有所縮小(通常是減半)； 二是相鄰兩次重復之間有緊密的聯系，前一次要為後一次做准備(通常前一次的輸出就作為後一次的輸入)； 三是在問題的規模極小時必須用直接給出解答而不再進行遞歸調用，因而每次遞歸調用都是有條件的(以規模未達到直接解答的大小為條件)，無條件遞歸調用將會成為死循環而不能正常結束。
舉例
描述：把一個整數按n(2<=n<=20)進製表示出來，並保存在給定字元串中。比如121用二進製表示得到結果為：「1111001」。 參數說明：s: 保存轉換後得到的結果。 n: 待轉換的整數。 b: n進制（2<=n<=20） void numbconv(char *s, int n, int b) { int len; if(n == 0) { strcpy(s, ""); return; } /* figure out first n-1 digits */ numbconv(s, n/b, b); /* add last digit */ len = strlen(s); s[len] = ""[n%b]; s[len+1] = '\0'; } void main(void) { char s[20]; int i, base; FILE *fin, *fout; fin = fopen("palsquare.in", "r"); fout = fopen("palsquare.out", "w"); assert(fin != NULL && fout != NULL); fscanf(fin, "%d", &base); /*PLS set START and END*/ for(i=START; i <= END; i++) { numbconv(s, i*i, base); fprintf(fout, "%s\n", s); } exit(0); }
編輯本段遞歸演算法簡析（PASCAL語言）
遞歸是計算機科學的一個重要概念,遞歸的方法是程序設計中有效的方法,採用遞歸編寫 程序能是程序變得簡潔和清晰.
一 遞歸的概念
1.概念 一個過程(或函數)直接或間接調用自己本身,這種過程(或函數)叫遞歸過程(或函數). 如: procere a; begin . . . a; . . . end; 這種方式是直接調用. 又如: procere c(形參);forward; procere b; 局部說明 begin . . c(實參); . . end; procere c; 局部說明； begin . . b; . . end; 這種方式是間接調用. 例1計算n!可用遞歸公式如下: fac:=n*fac(n-1) {當n>0時} fac(n)={ fac:=1; { 當n=0時} 可編寫程序如下: program facn; var n:integer; function fac(n:integer):real; begin if n=0 then fac:=1 else fac:=n*fac(n-1); end; begin write('n=');readln(n); writeln(n,'!=',fac(n):0:0); end. 例2 樓梯有n階台階,上樓可以一步上1階,也可以一步上2階,編一程序計算共有多少種不同的走法. 設n階台階的走法數為f(n) 顯然有 n=1 f(n)={ f(n-1)+f(n-2) n>2 可編程序如下： program louti; var n:integer; function f(x:integer):integer; begin if x=1 then f:=1 else if x=2 then f:=2 else f:=f(x-1)+f(x-2); end; begin write('n=');read(n); writeln('f(',n,')=',f(n)) end.
二 如何設計遞歸演算法
1.確定遞歸公式 2.確定邊界(終了)條件
三 典型例題
例3 漢諾塔問題 如圖:已知有三根針分別用1,2,3表示,在一號針中從小放n個盤子,現要求把所有的盤子 從1針全部移到3針,移動規則是:使用2針作為過度針,每次只移動一塊盤子,且每根針上 不能出現大盤壓小盤.找出移動次數最小的方案. 程序如下: program hanoi; var n:integer; procere move(n,a,b,c:integer); begin if n=1 then writeln(a,'->',c) else begin move(n-1,a,c,b); writeln(a,'--->',c); move(n-1,b,a,c); end; end; begin write('Enter n='); read(n); move(n,1,2,3); end. 例4 快速排序 快速排序的思想是:先從數據序列中選一個元素,並將序列中所有比該元素小的元素都放到它的右邊或左邊,再對左右兩邊分別用同樣的方法處之直到每一個待處理的序列的長度為1, 處理結束. 程序如下: program kspv; const n=7; type arr=array[1..n] of integer; var a:arr; i:integer; procere quicksort(var b:arr; s,t:integer); var i,j,x,t1:integer; begin i:=s;j:=t;x:=b ; repeat while (b[j]>=x) and (j>i) do j:=j-1; if j>i then begin t1:=b; b:=b[j];b[j]:=t1;end; while (b<=x) and (i<j) do i:=i+1; if i<j then begin t1:=b[j];b[j]:=b;b:=t1; end until i=j; b:=x; i:=i+1;j:=j-1; if s<j then quicksort(b,s,j); if i<t then quicksort(b,i,t); end; begin write('input data:'); for i:=1 to n do read(a); writeln; quicksort(a,1,n); write('output data:'); for i:=1 to n do write(a:6); writeln; end.
編輯本段{遞歸的一般模式}
procere aaa(k:integer); begin if k=1 then (邊界條件及必要操作) else begin aaa(k-1); (重復的操作); end; end;
開放分類：
編程，計算機，演算法

引自：http://ke..com/view/1733593.htm

⑤ 在遞歸演算法執行過程中,計算機系統必定會用到的數據結構是

指針

因為遞歸調用必然會用到函數指針對同一函數體進行反復的調用。

⑥ java中遞歸演算法是什麼怎麼算的

Java遞歸演算法是基於Java語言實現的遞歸演算法。遞歸演算法是一種直接或者間接調用自身函數或者方法的演算法。遞歸演算法實質是把問題分解成規模縮小的同類問題的子問題，然後遞歸調用方法表示問題的解。遞歸往往能給我們帶來非常簡潔非常直觀的代碼形式，從而使我們的編碼大大簡化，然而遞歸的思維確實跟我們的常規思維相逆的，通常都是從上而下的思維問題，而遞歸趨勢從下往上的進行思維。

二、遞歸演算法解決問題的特點：

【1】遞歸就是方法里調用自身。

【2】在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。

【3】遞歸演算法代碼顯得很簡潔，但遞歸演算法解題的運行效率較低。所以不提倡用遞歸設計程序。

【4】在遞歸調用的過程中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等，所以一般不提倡用遞歸演算法設計程序。

【5】在做遞歸演算法的時候，一定把握出口，也就是做遞歸演算法必須要有一個明確的遞歸結束條件。這一點是非常重要的。其實這個出口就是一個條件，當滿足了這個條件的時候我們就不再遞歸了。

三、代碼示例：

代碼執行流程圖如下：

此程序中n=5就是程序的出口。

⑦ 一個遞歸演算法必須包括什麼

遞歸演算法包含的兩個部分：

1、由其自身定義的與原始問題類似的更小規模的子問題（只有數據規模不同），它使遞歸過程持續進行，稱為一般條件。

2、所描述問題的最簡單的情況，它是一個能控制遞歸過程結束的條件，稱為基本條件。（遞歸出口）

遞歸的定義：

如果一個對象部分地由它自身組成或按它自己定義，則稱它是遞歸的，所以說遞歸就是函數/過程/子過程在運行過程中直接或間接調用自身而產生的重入現象。

遞歸的基本思想：

就是把一個規模大的問題分為若干個規模較小的子問題求解，而每一個子問題又可以分為幾個規模更小的子問題。基本上，所有的遞歸問題都可以用遞推公式來表示。

最重要的一點就是假設子問題已經解決了，現在要基於已經解決的子問題來解決當前問題；或者說，必須先解決子問題，再基於子問題來解決當前問題或者可以這么理解：遞歸解決的是有依賴順序關系的多個問題。

遞歸的優缺點：

優點：邏輯清楚，結構清晰，可讀性好，代碼簡潔，效率高（拓展：DFS深度優先搜素，前中後序二叉樹遍歷）

缺點：函數調用開銷大，空間復雜度高，有堆棧溢出的風險

⑧ 關於遞歸演算法

你輸入了三次，所以遞歸有三層，最外面一層是 a = A,程序停止在if(a!= '#') printf();
中間的一層是 a = B,程序同樣停止在if(a!= '#') printf(); 最裡面的一層，也就是你輸入a = #,
程序在判斷完兩個if後返回到上一層，if(a! ='#') printf("%c\n",a); 輸出 B ，然後再返回上一層輸出 A

⑨ 在遞歸演算法中 次數過多可能發生棧溢出，因為需要不斷在棧裡面存值如求階層return n*fun（n-1）/////

如果是不停的創建字元串，是會棧溢出的；但是這個int沒改一次值，只是改變了棧值，並沒有創建新的棧，我覺得只會發生值溢出，也就是已經超過int最大范圍了

⑩ 一個遞歸演算法必須包括什麼

一個遞歸演算法必須包括終止條件和遞歸部分。

遞歸演算法在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法。

遞歸式方法可以被用於解決很多的計算機科學問題，因此它是計算機科學中十分重要的一個概念。絕大多數編程語言支持函數的自調用，在這些語言中函數可以通過調用自身來進行遞歸。

能夠解決的問題：

數據的定義是按遞歸定義的。如Fibonacci函數。

問題解法按遞歸演算法實現。如Hanoi問題。

數據的結構形式是按遞歸定義的。如二叉樹、廣義表等。