遞歸詳解

遞歸

遞歸的算法思想

基本思想

把一個(gè)問題劃分為一個(gè)或多個(gè)規(guī)模更小的子問題，然后用同樣的方法解規(guī)模更小的子問題

遞歸算法的基本設(shè)計(jì)步驟

找到問題的初始條件（遞歸出口），即當(dāng)問題規(guī)模小到某個(gè)值時(shí)，該問題變得很簡(jiǎn)單，能夠直接求解

設(shè)計(jì)一個(gè)策略，用于將一個(gè)問題劃分為一個(gè)或多個(gè)一步步接近遞歸出口的相似的規(guī)模更小的子問題

將所解決的各個(gè)小問題的解組合起來，即可得到原問題的解

設(shè)計(jì)遞歸算法需要注意以下幾個(gè)問題

如何使定義的問題規(guī)模逐步縮小，而且始終保持同一問題類型？

每個(gè)遞歸求解的問題規(guī)模如何縮小？

多大規(guī)模的問題可作為遞歸出口？

隨著問題規(guī)模的縮小，能到達(dá)遞歸出口嗎？

遞歸設(shè)計(jì)實(shí)例

1. 計(jì)算 f(n) = 2n

f(n) = 2 × 2^n-1 = 2 × f(n-1) f(1) = 2¹ = 2

Program

f(n)

if n=0 then return 1

else return 2 * f(n-1)

2. Hanoi問題

將前n-1個(gè)圓盤從A柱借助于C搬到B柱

將最后一個(gè)圓盤直接從A柱搬到C柱

將n-1個(gè)圓盤從B柱借助于A柱搬到C柱

Hanoi(n, A, B, C)

if n=1 then move(1, A, C)

else

Hanoi(n-1, A, C, B)

move(1, A, C)

move(n-1, B, A, C)

T(n) = 2T(n-1) + 1

T(1) = 1

3. Selection sort

基本思想

把所有牌攤開，放在桌上，伸出左手，開始為空，準(zhǔn)備拿牌

將桌上最小額牌拾起，并把它插到左手所握牌的最右邊

重復(fù)上一步，直到桌上的所有牌都拿到你的左手上，此時(shí)左手上所握得牌便是排好序的牌

SelectionSort(i)

if i >= n then return 0

else

k = i

for j <- i+1 to n do

if A[j] < A[k] then

k <- j

if k != i then A[i] <-> A[k]

SelectionSort(i+1)

T(n) = T(n-1) + n

T(1) = 1

Java代碼實(shí)現(xiàn)

package sort; import java.util.Arrays; public class RecursiveSelectionSort { public static void main(String[] args) { double[] list = {3, 1, 5, 7, 2}; sort(list); /* for (int i = 0; i < list.length; i ++) System.out.print(list[i]+" "); */ System.out.println(Arrays.toString(list)); } public static void sort(double[] list) { sort(list, 0, list.length-1); } public static void sort(double[] list, int low, int high) { if (low < high) { double currentMin = list[low]; int currentMinIndex = low; for (int i = low+1; i <= high; i++) { if (currentMin > list[i]) { currentMin = list[i]; currentMinIndex = i; } } list[currentMinIndex] = list[low]; list[low] = currentMin; sort(list, low+1, high); } } }

4. 生成排列

問題是生成{1, 2, …, n}的所有n!排序

假設(shè)我們能夠生成n-1個(gè)元素的所有排列，我們可以得到如下算法：

生成元素{2, 3, …, n}的所有排列，并且將元素 1 放到每個(gè)排列的開頭

接著，生成元素{1, 3, …, n}的所有排列，并且將元素 2 放到每個(gè)排列的開頭

重復(fù)這個(gè)過程，直到元素{2, 3, …, n-1}的所有排列都產(chǎn)生，并將元素 n 放到每個(gè)排列的開頭

GeneratingPerm1() for j <- 1 to n do P[j] <- j Perm1() Perm1(m) if m = n then output P[1...n] else for j <- m to n do P[j] <-> P[m] Perm1(m+1) P[j] <-> P[m]

T(n) = nT(n-1) + n

首先，我們把 n 放在位置P[1]上，并且用子數(shù)組P[2…n] 來產(chǎn)生前 n-1 個(gè)數(shù)的排列

接著，我們將 n 放在P[2]上，并且用子數(shù)組P[1]和P[3…n]來產(chǎn)生前 n-1 個(gè)數(shù)的排列

然后，我們將 n 放在P[3]上，并且用子數(shù)組P[1…2]和P[4…n]來產(chǎn)生前 n-1 個(gè)數(shù)的排列

重復(fù)上述過程直到我們將 n 放在P[n]上，并且用子數(shù)組P[1…n-1]來產(chǎn)生前 n-1 個(gè)數(shù)的排列

GeneratingPerm2() for j<-1 to n do p[j]<-0 Perm2(n) Perm2(m) if m = 0 then ouput P[1 ... n] else for j<-1 to n do if P[j]=0 then P[j]<-m Perm2(m-1) P[j]<-0

遞歸方程求解

公式法

對(duì)于下列形式的遞歸方程

T(n) = aT(n/b) + f(n)

其中 a >= 1, b > 1是常數(shù)，f(n)是一個(gè)漸進(jìn)正函數(shù)，可以使用公式法(Master Method) 方便快捷地求得遞歸方程地解

將一個(gè)規(guī)模為n的問題劃分成a個(gè)規(guī)模為n/b的子問題，其中a和b為正常數(shù)，分別遞歸地解決a個(gè)子問題，解每個(gè)子問題所需時(shí)間為T(n/b)，劃分原問題和合并子問題的解所需的時(shí)間由f(n)決定

令 a >= 1和b > 1 是常數(shù)，f(n)是一個(gè)正函數(shù)，T(n)滿足

T(n) = aT(n/b) + f(n)

其中n/b表示[n/b]或者[n/b], 則T(n)有如下三種情況的漸進(jìn)界

if f(n) = O(nlogba-

ε

\varepsilon

ε), for some constant

ε

\varepsilon

ε > 0, then T(n) =

Θ

\Theta

Θ(nlogba)

if f(n) =

Θ

\Theta

Θ(nlogba), then T(n) =

Θ

\Theta

Θ(nlogba lgn)

if f(n) =

Ω

\Omega

Ω(nlogba+

ε

\varepsilon

ε), for some constant

ε

\varepsilon

ε > 0, and if af(n/b) &\leq& cf(n) for some c < 1 and all sufficiently large n, then T(n) =

Θ

\Theta

Θ(f(n))

案例

T(n) = 9T(n/3) + n, a = 9, b = 3, f(n) = n, and nlogba = nlog39 = n2

f(n) = O(nlogba-

ε

\varepsilon

ε) = O(nlog39-1)

T(n) =

Θ

\Theta

Θ(n2)

T(n) = T(2n/3) + 1, a = 1, b = 3/2, f(n) = 1, and nlogba = nlog3/21 = n0 = 1

f(n) =

Θ

\Theta

Θ(nlogba) =

Θ

\Theta

Θ(1)

T(n) =

Θ

\Theta

Θ(lgn)

T(n) = T(n-1) + n, f(n) = n, a = b = 1, 不可應(yīng)用此方法

數(shù)據(jù)結(jié)構(gòu)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。