Phần 2: dùng stack để khử thuật tóan đệ quy nhánh
Như chúng ta đã biết, sự thực hiện của đệ quy chính là sự thực hiện lại chính bản thân
nó với dữ liệu nhỏ hơn, nên khi gọi hàm đệ quy thì máy sẽ cấp phát một vùng nhớ có cơ
chế hoạt động như Stack (ngăn xếp) cho hàm đệ quy đó. Cơ chế này hoạt động như kiểu
LIFO( last in first out – vào sau ra trước), tức là việc thêm vào hay lấy ra đều thực hiện
thông qua một đầu ra duy nhất
Nếu một chương trình con đệ qui P(x) được gọi từ chương trình chính ta nói chương
trình con được thực hiện ở mức 1. Chương trình con này gọi chính nó, ta nói nó đi sâu
vào mức 2 và cho đến một mức k. Rõ ràng mức k phải thực hiện xong thì mức k-1 mới
được thực hiện tiếp tục, hay ta còn nói là chương trình con quay về mức k-1.
Trong khi một chương trình con từ mức i đi vào mức i+1 thì các biến cục bộ của mức i
và địa chỉ của mã lệnh còn dang dở phải được lưu trữ, địa chỉ này gọi là địa chỉ trở về.
Khi từ mức i+1 quay về mức i các giá trị đó được sử dụng. Như vậy những biến cục bộ
và địa chỉ lưu sau được dùng trước. Tính chất này gợi ý cho ta dùng một stack để lưu giữ
các giá trị cần thiết của mỗi lần gọi tới chương trình con như biến cục bộ, các tham số.
Mỗi khi lùi về một mức thì các giá trị này được lấy ra để tiếp tục thực hiện mức này. Ta
tóm tắt quá trình:
•  Bưóc 1: Tạo 1 stack rỗng
•  Bưóc 2: Lưu các tham số hình thức ở mức 1 vào stack.
•  Bước 3: Lặp cho đến khi stack rỗng
1. Lấy ra 1 phần tử X khỏi stack
Vào sau
Vào trước
vào
ra
Đỉnh
Stack(Ngăn xếp)
2. Nếu X thoả điều kiện dừng của đệ qui (NEO) thì xử lý dữ liệu
Ngược lại (phần đệ qui)
Xử lý theo thuật tóan
Xác định lời gọi đệ quy với các tham số tương ứng và

move(3,A,B,C) Move(1,A,B,C) A->B
Move(1,C,A,B) C->A
Move(2,C,B,A) Move(1,C,B,A) C->B
Move(1,A,B,C) A->B
Mức 1 mức 2 mức 3
Cây đệ quy trên được mô phỏng qua việc dùng stack để giải quyết như sau:
(3,A,B,C) (2,A,C,B) Quá trình chuyển đĩa
(2,B,A,C)
Từ đây, ta xây dựng cấu trúc của mỗi phần tử được lưu trong stack để giải quyết bài toán
tháp Hà nội như sau:
struct Item_Tower{
int num; // số đĩa
char sour, midl, dest;
void assign(int n, char a, char b, char c){ // hàm gán từng giá trị cho các thuộc tính
num = n; sour = a; midl = b, dest = c;
}
};
3 A B C
A->C
A->B
C->B
A->C
B->A
B->C
A->C
ACBABCBAC ABCACBCABA
BCBAC
BAC
BCABACABC
Thuật toán khử đệ qui

sau đó dùng các con tromino phủ đầy bàn cờ.

Với bàn cờ cỡ n= 8
Thuật tóan:
Từ bàn cờ kích thước cỡ 2
n
* 2
n
với n>0 và 1 ô có tọa độ (x,y) bị đánh dấu, ta chia bàn cờ
thành 4 bàn cờ con, với tâm bàn cờ là 1 con tromino có phần khuyết hướng về phía ô bị
đánh dấu
Như vậy ta được 4 bàn cờ con, mỗi bàn cờ con có kích thước 2
n-1
* 2
n-1
với 1 ô bị đánh
dấu, vì mỗi góc của con tromino vừa đặt vào tâm trở thành ô bị đánh dấu trong mỗi bàn
cờ con mới.
X
X
X X
Với mỗi bàn cờ con, ta lại tiếp tục thực hiện cho đến khi mọi ô trong bàn cờ bị đánh dấu.
Như vậy, bài toán này trở thành 4 bài toán con tương tự với 4 lần gọi đệ quy
Thuật toán
Proc Tromino( {a, b}, {x, y}, n)
/* trong do {a, b} là tọa độ góc trên bến trái của bàn cờ
{x, y} là tọa độ ô bị đánh dấu
n là kích thước của bàn cờ */
if(n>1){
s = n/2 ; // slà kích thước của 4 bàn cờ con

3
}, {x
3
, y
3
}, s);
call Tromino({a
4
,b
4
}, {x
4
, y
4
}, s);
,
}
Return
Từ đây, ta xây dựng cấu trúc của mỗi phần tử được lưu trong stack để giải quyết bài
Tromino như sau:
struct Item_Tromino{
int a, b, x, y, n;
void assign(int a1, int b1, int x1, int y1, int n1){
a = a1, b = b1, x = x1, y = y1, n = n1;
}
};
void Tromino(){
Stack <Item_Tromino> sTromino;
Item_Tromino t;
// đưa dữ liệu của bàn cờ đầu tiên vào stack

}{x
i
, y
i
}, s) vào stack
t.assign(a4,b4,x4,y4,s); // góc phần tư thứ 4
sTromino.push(t);
t.assign(a3,b3,x3,y3,s); // góc phần tư thứ 3
sTromino.push(t);
t.assign(a2,b2,x2,y2,s); // góc phần tư thứ 2
sTromino.push(t);
t.assign(a1,b1,x1,y1,s); // góc phần tư thứ 1
sTromino.push(t);
}
}
}
Một kết quả khi chạy chương trình
Ví dụ 3:Thuật toán QuickSort
Mục đích: Sắp xếp dãy khoá có n phần tử M
l
, M
l+1
, M
l+2
,…,M
h
(n=h-l+1) theo thứ tự
tăng dần với độ phức tạp O(nlgn)
Đầu vào: dãy M
l

có n phần tử được phân hoạch lại
thành 2 dãy con không trống là dãy M
l
,…,M
pos-1
và M
pos+1
,…,M
h
cỡ
n/2 phần tử sao cho mỗi thành phần của dãy M
l
,…,M
pos-1
nhỏ hơn
M
pos
và mỗi thành phần của dãy M
pos+1
,…,M
h
lớn hơn hoặc bằng M
pos
.
Vị trí pos là kết quả của quá trình phân hoạch
• Trị: Hai dãy con M
l
,…,M
pos-1
và M

.
Các khoá này nằm bên phải của
X trong dãy
M
l
M
l+
… … M
pos-
X M
pos+
… … … … M
h
Các khoá < M
pos
Pos
Các khoá ≥ M
pos
Func Partition(low, hight) // low chỉ số cận trái và hight chỉ số cận phải của dãy
X = M
low
// X là giá trị được dùng để phân hoạch thành 3 dãy con
last_small = low //là chỉ số cuối cùng của dãy <=X
i = low+1
While i ≤ hight Do
{
If M
i
<X Then
{

phân hoạch đối với dãy có hơn 1 giá trị
Mỗi phần tử của stack được định nghĩa như sau:
struct Item_QS{
int left, right;
void assign(int a, int b){
left = a; right = b;
}
};
Thuật toán quicksort không đệ qui như sau:
void quicksort( int l, int r ){
Stack<Item_QS> sQS;
Item_QS t;
t.assign(l, r);
sQS.push(t); // đưa chỉ số cận trái và cận phải vào stack
while(sQS.isEmpty()==false)
{ Item_QS temp;
temp = sQS.topOfStack(); // lấy ra cặp chỉ số của dãy
sQS.pop();
if (temp.left < temp.right){
int pos = partition(temp.left, temp.right);
if(pos+1 < temp.right){ // nếu dãy con bên phải có >1 phần tử
t.assign(pos +1, temp.right);
sQS.push(t); // đưa cặp chỉ số dãy con bên phải vào stack
}
if(temp.left < pos-1){ // nếu dãy con bên trái có >1 phần tử
t.assign(temp.left, pos -1);
sQS.push(t); // đưa cặp chỉ số dãy con bên phải vào stack
}
}
}