同壹問題可能既可以用遞歸算法解決,也可以用非遞歸算法解決,遞歸往往算法設計簡單,出奇制勝,而普通算法(通常用循環解決)往往設計稍復雜。但執行效率遞歸算法遜於循環算法。遞歸反復調用自己,需要占用較多內存和計算機時間。但有壹些問題只有用遞歸方法才能解決,如著名的漢諾塔問題。
遞歸程序設計的關鍵就是考慮問題的兩種情況,壹種是普遍情況即函數值等於把問題遞推壹步後的本函數的調用,壹種是極端或端點情況,此時函數值有確定的壹個值而無須再調用本函數。遞歸的過程就是從普遍情況逐步過渡到端點情況的過程。
例子:
5個坐在壹起論年齡,問第五個人多少歲?他說比第四個人大兩歲。問第四個人多少歲,他說比第三個人大兩歲。問第三個人多少歲,他說比第二個人大兩歲。問第二個人多少歲,他說比第壹個人大兩歲。問第壹個人多少歲,他說10歲。請問第五個人幾歲?
int age(int n)
{ int x;
if(n>1) x=age(n-1)+2;
else if(n==1) x=10;
return x;
}
void main( )
{ printf(%d,age(5));}
問題二:什麽是遞歸算法 遞歸算法就是壹個函數通過不斷對自己的調用而求得最終結果的壹種思維巧妙但是開銷很大的算法。
比如:
漢諾塔的遞歸算法:
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塊借助hanno處函數的功能從B由A搬回到C 這樣的三步實習了n塊由A經過B到C這樣壹個功能,同樣妳不用糾結於hanoi函數到底如何實現這個功能的,只要知道他有這麽壹個神奇的功能就行
最後:遞歸都有收尾的時候對吧,收尾就是當只有壹塊的時候漢諾塔怎麽個玩法呢?很簡單吧,直接把那壹塊有Amove到C我們就完成了,所以hanoni這個函數最後還要加上 if(n==1)move(one,three);(當只有壹塊時,直接有Amove到C位置就行)這麽壹個條件就能實現hanoin函數n>=1時......>>
問題三:怎麽更好地終極理解遞歸算法 遞歸的基本思想是把規模大的問題轉化為規模小的相似的子問題來解決。在函數實現時,因為解決大問題的方法和解決小問題的方法往往是同壹個方法,所以就產生了函數調用它自身的情況。另外這個解決問題的函數必須有明顯的結束條件,這樣就不會產生無限遞歸的情況了。
需註意的是,規模大轉化為規模小是核心思想,但遞歸並非是只做這步轉化,而是把規模大的問題分解為規模小的子問題和可以在子問題解決的基礎上剩余的可以自行解決的部分。而後者就是歸的精髓所在,是在實際解決問題的過程。
問題四:怎樣才能深刻理解遞歸和回溯? 遞歸的精華就在於大問題的分解,要學會宏觀的去看問題,如果這個大問題可分解為若幹個性質相同的規模更小的問題,那麽我們只要不斷地去做分解,當這些小問題分解到我們能夠輕易解決的時候,大問題也就能迎刃而解了。如果妳能獨立寫完遞歸創建二叉樹,前序、中序、後序遞歸遍歷以及遞歸計算二叉樹的最大深度,遞歸就基本能掌握了。
回溯本人用得很少,僅限於八皇後問題,所以幫不上啥了。
問題五:二叉樹的遞歸算法到底該怎麽理解 這不就是在二叉排序樹上的遞歸查找,看程序
tree& find(const T& d, tree& t){
if(t==NULL) return t;如果二叉樹為空則返回空,查找失敗
if(t->data==d) return t;否則,如果當前根結點關鍵碼為d,則查找成功,當前根結點為待查找結點
if(d>t->data) return find(d, t->right);如果比根的關鍵碼大就遞歸查找右子樹
return find(d, t->left);如果比根的關鍵碼小就遞歸查找左子樹
}
二叉樹的遞歸定義的含義就是非空二叉樹,除了根以外,左右子樹都是二叉樹(可以為空)
問題六:怎麽理解遞歸算法?我看了代碼但還是不理解? 函數自己調用自己就是遞歸啊。
從前有座山,山裏有座廟,廟裏有個老和尚給小和尚講故事。講的內容是:
從前有座山,山裏有座廟,廟裏有個老和尚給小和尚講故事,講
從前有座山,山裏有座廟,廟裏有個老和尚給小和尚講故事……
跟循環差不多。而且浪費棧空間,效率不高。能夠轉化為循環最好。
問題七:數據結構中的二叉樹中的遞歸怎麽理解? 以中序遍歷為例,思想是:
若二叉樹為空,則空操作;否則
(1)中序遍歷左子樹
(中序遍歷左子樹時也是這三步)
(2)訪問根結點
(3)中序遍歷右子樹
(當然右子樹也是重復著三步)
示例代碼:
int InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lchild);
printf(%d\t,T->data);
InOrderTraverse(T->rchild);
}
return OK;
}
問題八:java遞歸算法,怎麽理解? n! = (n-1)*n!
簡單理解,就是目前的所有任務,等於前面所有的任務+現在的任務。
比如妳求 1。。。100的加法總和
實際上是 1... 99 的加法總和 + 100 就是了。
這就是遞歸的來源。
妳只需要計算妳前壹步的任務,然後加上自己,就OK了。
前壹步,在再次調用前前壹步......
問題九:新手壹個,有什麽更好理解遞歸的方法嗎?(c++) 遞歸的話就是重復調用方法直到滿足條件為止就停止這個方法,就跟循環類似,不過循環使用的方法壹邊比較簡單
問題十:遞歸的原理解釋 遞歸的底層實現其實是壹個棧.棧的特點是後進先出,也就是最後進入棧的事件是最先被處理的.
遞歸就是這樣運作.比如計算階乘函數F(n)=n!=n*F(n-1)=....
寫成遞歸,我用java
public static long F(long num){
if(num