(1) 遞迴執行過程
例子：求N!。
這是一個簡單的"累乘"問題，用遞迴演算法也能解決。
n! = n * (n - 1)! n > 1
0! = 1, 1! = 1 n = 0,1
因此，遞迴演算法如下：
Java程式碼
fact(int n) {
if(n == 0 || n == 1)
return 1;
else
return n * fact(n - 1);
}
以n=3為例，看執行過程如下：
fact(3) ----- fact(2) ----- fact(1) ------ fact(2) -----fact(3)
------------------------------> ------------------------------>
遞迴 回溯
遞迴演算法在執行中不斷呼叫自身降低規模的過程，當規模降為1，即遞迴到fact(1)時，滿足停止條件停止遞迴，開始回溯(返回呼叫演算法)並計算，從fact(1)=1計算返回到fact(2);計算2*fact(1)=2返回到fact(3)；計算3*fact(2)=6，結束遞迴。
演算法的起始模組也是終止模組。
(2) 遞迴實現機制
每一次遞迴呼叫，都用一個特殊的資料結構"棧"記錄當前演算法的執行狀態，特別地設定地址棧，用來記錄當前演算法的執行位置，以備回溯時正常返回。遞迴模組的形式引數是普通變數，每次遞迴呼叫得到的值都是不同的，他們也是由"棧"來儲存。
(3) 遞迴呼叫的幾種形式
一般遞迴呼叫有以下幾種形式(其中a1、a2、b1、b2、k1、k2為常數)。
<1> 直接簡單遞迴呼叫： f(n) {...a1 * f((n - k1) / b1); ...};
<2> 直接複雜遞迴呼叫： f(n) {...a1 * f((n - k1) / b1); a2 * f((n - k2) / b2); ...};
<3> 間接遞迴呼叫： f(n) {...a1 * f((n - k1) / b1); ...}，
g(n) {...a2 * f((n - k2) / b2); ...}。
2. 遞迴演算法效率分析方法
遞迴演算法的分析方法比較多，最常用的便是迭代法。
迭代法的基本步驟是先將遞迴演算法簡化為對應的遞迴方程，然後透過反覆迭代，將遞迴方程的右端變換成一個級數，最後求級數的和，再估計和的漸進階。
<1> 例：n!
演算法的遞迴方程為： T(n) = T(n - 1) + O(1);
迭代展開： T(n) = T(n - 1) + O(1)
= T(n - 2) + O(1) + O(1)
= T(n - 3) + O(1) + O(1) + O(1)
= ......
= O(1) + ... + O(1) + O(1) + O(1)
= n * O(1)
= O(n)
這個例子的時間複雜性是線性的。
<2> 例：如下遞迴方程：
T(n) = 2T(n/2) + 2, 且假設n=2的k次方。
T(n) = 2T(n/2) + 2
= 2(2T(n/2*2) + 2) + 2
= 4T(n/2*2) + 4 + 2
= 4(2T(n/2*2*2) + 2) + 4 + 2
= 2*2*2T(n/2*2*2) + 8 + 4 + 2
= ...
= 2的(k-1)次方 * T(n/2的(i-1)次方) + $(i:1~(k-1))2的i次方
= 2的(k-1)次方 + (2的k次方) - 2
= (3/2) * (2的k次方) - 2
= (3/2) * n - 2
這個例子的時間複雜性也是線性的。
<3> 例：如下遞迴方程：
T(n) = 2T(n/2) + O(n), 且假設n=2的k次方。
T(n) = 2T(n/2) + O(n)
= 2T(n/4) + 2O(n/2) + O(n)
= O(n) + O(n) + ... + O(n) + O(n) + O(n)
= k * O(n)
= O(k*n)
= O(nlog2n) //以2為底
一般地，當遞迴方程為T(n) = aT(n/c) + O(n), T(n)的解為：
O(n) (a<c && c>1)
O(nlog2n) (a=c && c>1) //以2為底
O(nlogca) (a>c && c>1) //n的(logca)次方，以c為底
上面介紹的3種遞迴呼叫形式，比較常用的是第一種情況，第二種形式也有時出現，而第三種形式(間接遞迴呼叫)使用的較少，且演算法分析
比較複雜。 下面舉個第二種形式的遞迴呼叫例子。
<4> 遞迴方程為：T(n) = T(n/3) + T(2n/3) + n
為了更好的理解，先畫出遞迴過程相應的遞迴樹：
n --------> n
n/3 2n/3 --------> n
n/9 2n/9 2n/9 4n/9 --------> n
...... ...... ...... ....... ......
--------
總共O(nlogn)
累計遞迴樹各層的非遞迴項的值，每一層和都等於n，從根到葉的最長路徑是：
n --> (2/3)n --> (4/9)n --> (12/27)n --> ... --> 1
設最長路徑為k，則應該有：
(2/3)的k次方 * n = 1
得到 k = log(2/3)n // 以(2/3)為底
於是 T(n) <= (K + 1) * n = n (log(2/3)n + 1)
即 T(n) = O(nlogn)
由此例子表明，對於第二種遞迴形式呼叫，藉助於遞迴樹，用迭代法進行演算法分析是簡單易行的。
(1) 遞迴執行過程
例子：求N!。
這是一個簡單的"累乘"問題，用遞迴演算法也能解決。
n! = n * (n - 1)! n > 1
0! = 1, 1! = 1 n = 0,1
因此，遞迴演算法如下：
Java程式碼
fact(int n) {
if(n == 0 || n == 1)
return 1;
else
return n * fact(n - 1);
}
以n=3為例，看執行過程如下：
fact(3) ----- fact(2) ----- fact(1) ------ fact(2) -----fact(3)
------------------------------> ------------------------------>
遞迴 回溯
遞迴演算法在執行中不斷呼叫自身降低規模的過程，當規模降為1，即遞迴到fact(1)時，滿足停止條件停止遞迴，開始回溯(返回呼叫演算法)並計算，從fact(1)=1計算返回到fact(2);計算2*fact(1)=2返回到fact(3)；計算3*fact(2)=6，結束遞迴。
演算法的起始模組也是終止模組。
(2) 遞迴實現機制
每一次遞迴呼叫，都用一個特殊的資料結構"棧"記錄當前演算法的執行狀態，特別地設定地址棧，用來記錄當前演算法的執行位置，以備回溯時正常返回。遞迴模組的形式引數是普通變數，每次遞迴呼叫得到的值都是不同的，他們也是由"棧"來儲存。
(3) 遞迴呼叫的幾種形式
一般遞迴呼叫有以下幾種形式(其中a1、a2、b1、b2、k1、k2為常數)。
<1> 直接簡單遞迴呼叫： f(n) {...a1 * f((n - k1) / b1); ...};
<2> 直接複雜遞迴呼叫： f(n) {...a1 * f((n - k1) / b1); a2 * f((n - k2) / b2); ...};
<3> 間接遞迴呼叫： f(n) {...a1 * f((n - k1) / b1); ...}，
g(n) {...a2 * f((n - k2) / b2); ...}。
2. 遞迴演算法效率分析方法
遞迴演算法的分析方法比較多，最常用的便是迭代法。
迭代法的基本步驟是先將遞迴演算法簡化為對應的遞迴方程，然後透過反覆迭代，將遞迴方程的右端變換成一個級數，最後求級數的和，再估計和的漸進階。
<1> 例：n!
演算法的遞迴方程為： T(n) = T(n - 1) + O(1);
迭代展開： T(n) = T(n - 1) + O(1)
= T(n - 2) + O(1) + O(1)
= T(n - 3) + O(1) + O(1) + O(1)
= ......
= O(1) + ... + O(1) + O(1) + O(1)
= n * O(1)
= O(n)
這個例子的時間複雜性是線性的。
<2> 例：如下遞迴方程：
T(n) = 2T(n/2) + 2, 且假設n=2的k次方。
T(n) = 2T(n/2) + 2
= 2(2T(n/2*2) + 2) + 2
= 4T(n/2*2) + 4 + 2
= 4(2T(n/2*2*2) + 2) + 4 + 2
= 2*2*2T(n/2*2*2) + 8 + 4 + 2
= ...
= 2的(k-1)次方 * T(n/2的(i-1)次方) + $(i:1~(k-1))2的i次方
= 2的(k-1)次方 + (2的k次方) - 2
= (3/2) * (2的k次方) - 2
= (3/2) * n - 2
= O(n)
這個例子的時間複雜性也是線性的。
<3> 例：如下遞迴方程：
T(n) = 2T(n/2) + O(n), 且假設n=2的k次方。
T(n) = 2T(n/2) + O(n)
= 2T(n/4) + 2O(n/2) + O(n)
= ...
= O(n) + O(n) + ... + O(n) + O(n) + O(n)
= k * O(n)
= O(k*n)
= O(nlog2n) //以2為底
一般地，當遞迴方程為T(n) = aT(n/c) + O(n), T(n)的解為：
O(n) (a<c && c>1)
O(nlog2n) (a=c && c>1) //以2為底
O(nlogca) (a>c && c>1) //n的(logca)次方，以c為底
上面介紹的3種遞迴呼叫形式，比較常用的是第一種情況，第二種形式也有時出現，而第三種形式(間接遞迴呼叫)使用的較少，且演算法分析
比較複雜。 下面舉個第二種形式的遞迴呼叫例子。
<4> 遞迴方程為：T(n) = T(n/3) + T(2n/3) + n
為了更好的理解，先畫出遞迴過程相應的遞迴樹：
n --------> n
n/3 2n/3 --------> n
n/9 2n/9 2n/9 4n/9 --------> n
...... ...... ...... ....... ......
--------
總共O(nlogn)
累計遞迴樹各層的非遞迴項的值，每一層和都等於n，從根到葉的最長路徑是：
n --> (2/3)n --> (4/9)n --> (12/27)n --> ... --> 1
設最長路徑為k，則應該有：
(2/3)的k次方 * n = 1
得到 k = log(2/3)n // 以(2/3)為底
於是 T(n) <= (K + 1) * n = n (log(2/3)n + 1)
即 T(n) = O(nlogn)
由此例子表明，對於第二種遞迴形式呼叫，藉助於遞迴樹，用迭代法進行演算法分析是簡單易行的。