分析遞歸算法三種方法
替換法、疊代法、通用法（master method）
作用：分析遞歸算法的運作時間
分治算法
将一個問題分解為與原問題相似但規模更小的若幹子問題，遞歸地解這些子問題，然後将這些子問題的解結合起來構成原問題的解。這種方法在每層遞歸上均包括三個步驟：
divide（分解）：将問題劃分為若幹個子問題
conquer（求解）：遞歸地解這些子問題；若子問題size足夠小，則直接解決之
combine（組合）：将子問題的解組合成原問題的解
其中的第二步很關鍵：遞歸調用或直接求解 （遞歸終結條件），且有的算法“分解”容易，有的則“組合”容易
分治法舉例：
歸并排序
①分解：把n個待排序元素劃分為兩個size為n/2的子序列
②求解：遞歸調用歸并排序将這兩個子序列排序，若子序列長度為1時，已自然有序，無需做任何事情（直接求解）
③組合：将這兩個已排序的子序列合并為一個有序的序列
顯然，分解容易（一分為二），組合難。
快速排序
剛剛分析過了，快速排序是樞軸記錄劃分，也就是分解難，但是組合易。 a[1…k-1] ≤ a[k] ≤ a[k+1…n]
分治算法分析
設t(n)是size為n的執行時間，若size足夠小，如n ≤ c (常數)，則直接求解的時間為θ(1)
①設完成劃分的時間為d(n)
②設分解時，劃分為a個子問題，每個子問題為原問題的1/b，則解各子問題的時間為at(n/b)
③設組合時間c(n)
一般地，遞歸的求解劃分，而解遞歸式時可忽略細節
①假定函數參數為整數，如
②邊界條件可忽略，當n較小時，t(n）= θ(1)
因為這些細節一般隻影響常數因子的大小，不改變量級。求解時，先忽略細節，然後再決定其是否重要！
分析的方法
替換法
猜測解，用數學歸納法确定常數c，證明解正确，關鍵步驟是用猜測的解代入到遞歸式中。
做出好的猜測（沒有一般方法，隻能憑經驗）
①與見過的解類似，則猜測之。
②先證較寬松的上、下界，減小猜測範圍。
細節修正
有時猜測解是正确的，但數學歸納法卻不能直接證明其細節，這是因為數學歸納法不是強大到足以證明其細節。這時可從猜測解中減去一個低階項以使數學歸納法得以滿足
避免陷阱
與求和式的數學歸納法類似，證明時漸近記号的使用易産生錯誤。
變量變換
有時改動變量能使未知遞歸式變為熟悉的式子。例如：
疊代法
展開：無須猜測，展開遞歸式，使其成為僅依賴于n和邊界條件的和式，然後用求和方法定界。需要關注：
1、達到邊界條件所需的疊代次數
2、疊代過程中的和式。若在疊代過程中已估計出解的形式，亦可用替換法
3、當遞歸式中包含floor和ceiling函數時，常假定參數n為一個整數次幂，以簡化問題。
遞歸樹
使展開過程直覺化
例： t(n)=2t(n/2)+n^2 （不妨設n=2k）
the master method（通用法，萬能法）
可迅速求解
t(n)=at(n/b)+f(n) //常數a ≥1, b>1, f(n)漸近正
意義：将size為n的問題劃分為a個子問題，每個子問題size為n/b。每個子問題的時間為t(n/b)，劃分和combine的時間為f(n)。
注意：n/b不一定為整數，應為⌊n/b⌋或⌈n/b⌉，不會影響漸近界。
關于遞歸和循環的了解與比較
遞歸通俗的說就是一個函數調用函數自己（本身），這個調用過程叫遞歸，遞歸是一把雙刃劍（有時友善，有時不好），如果需要處理重複的需要多次計算的問題，通常可以選擇用遞歸或者循環兩種方式，但是遞歸的執行效率不如循環語句。
注意：必須設定終止遞歸的條件檢測，否則慎用。
首先，main函數用參數1調用遞歸函數，遞歸函數形參n=1，列印語句level1……然後，n<4，故函數本身使用參數n+1=2,第二次調用自己，這樣就列印了level2……
以此類推，當執行到第四級調用，n=4，if失效，不再調用函數，而是執行了第二句列印，先輸出level4……此時第四級調用結束，控制權傳回給了主調函數，也就是第三級主調函數，此函數中上一句是if語句，已經執行完畢，然後繼續執行第二句列印語句，輸出level3……第三級調用結束，傳回控制權給調用函數（也就是第二級主調函數），然後第二級函數開始繼續執行，以此類推，列印level2,1……
遞歸的基本原理
每一級遞歸都使用自己這一級的私有變量n，同級調用時的位址和傳回的位址是一樣的。好好揣摩！
這是函數自己在一層層的往深度調用自己，然後一層層的往回返，每到一層，就繼續執行接下來的語句（故調用開始的位址和傳回的位址一樣），而每一級遞歸都是用自己的局部變量。也就是第一級的n不同于第二級的n，這樣子，函數逐漸調用然後逐漸傳回直到main函數裡。
遞歸函數裡，遞歸語句之前的語句和各級被調的遞歸函數執行順序一緻，而遞歸語句之後的語句和被調的遞歸函數執行順序相反（這一特點針對涉及反向順序的程式設計問題很有用）
遞歸函數必須包含可以終止的條件，因為遞歸可以替代循環，故必須有終止
尾遞歸
最簡單的遞歸：遞歸語句放到函數末尾，恰在return語句前，叫做tail recursion（尾遞歸），因為出現在函數尾部，作用相當于一條循環語句。
注意:整型範圍，32位機器，int類型最大到21多億，再大的話，就要用long long或者double類型，一般來說，選擇循環比較好些，遞歸每次調用都要有自己的變量集合，占據記憶體大，每次都要存儲新的變量集合到堆棧，這樣速度慢，但是遞歸（最簡單的是尾遞歸）比較簡單。一些情況還是要用。
辛苦的勞動，轉載請注明出處，謝謝……
http://www.cnblogs.com/kubixuesheng/p/4355060.html