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à

nạp các tham số đó vào stack
 Bước 4: Kết thúc thuật toán
Một số ví dụ về dùng Stack để khử đệ qui
Ví dụ 1: Bài toán Tháp Hà Nội
Có ba cọc A,B,C. Khởi đầu cọc A có một số đĩa xếp theo thứ tự nhỏ dần lên trên đỉnh.
Bài toán đặt ra là phải chuyển toàn bộ chồng đĩa từ A sang C. Mỗi lần thực hiện chuyển
một đĩa từ một cọc sang một cọc khác và không được đặt đĩa lớn nằm trên đĩa nhỏ
Phân tích bài toán:
Trường hợp 1 đĩa: Chuyển thẳng từ A sang C. Đây là trường hợp suy biến
Trường hợp 2 đĩa: Chuyển 1 đĩa từ A sang B
Chuyển 1 đĩa từ A sang C
Chuyển 1 đĩa từ B sang C
Trường hợp chung n>1 đĩa; Ta coi n-1 đĩa trên như là 1 đĩa và ta áp dụng trong trường
hợp 2 đĩa
 Chuyển n-1 đĩa từ A sang B ( dùng cọc C làm trung gian)
 Chuyển 1 đĩa từ A sang C
 Chuyển n-1 đĩa từ B sang C (dùng cọc A làm trung gian)
thuật toán đệ qui mô phỏng như sau:
Proc Move(n,A,B,C) // Chuyển n đĩa từ cọc A sang cọc C
If n=1 Then
chuyển (A,’’,C)
Else { Call Move(n-1, A, C, B)
Call Move(1, A, B, C)
Call Move(n-1, B, A, C)
}
Return
Quá trình thực hiện chương trình con được minh hoạ với 3 đĩa (n=3) như sau:
Move(1,A,B,C) A->B
Move(2,A,C,B) Move(1,A,C,B) A->C
Move(1,B,C,A) B->C

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

void haNoi_Tower(int n, char a, char b, char c){
Stack<Item_Tower> sTower; // Khai báo stack kiểu Item_Tower
Item_Tower t;
int d = 0;
t.assign(n, a, b, c);
sTower.push(t);
while (sTower.isEmpty() == false){
Item_Tower temp = sTower.topOfStack();
sTower.pop();
if(temp.num == 1) cout<<" \n "<<++d<<" ."<<temp.sour <<" >"<<temp.dest;
else{
t.assign(temp.num-1, temp.midl, temp.sour, temp.dest);
sTower.push(t);
t.assign(1, temp.sour, temp.midl, temp.dest);
sTower.push(t);
t.assign(temp.num - 1, temp.sour, temp.dest, temp.midl);
sTower.push(t);
}
}
}
Ví dụ 2: Phủ bàn cờ kích thước 2
n
* 2
n
bằng các con tromino
Yêu cầu: có bàn cờ kích thước 2
n
* 2
n
(n nguyên >0). Đánh dấu 1 ô bất kỳ trên bàn cờ,

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

xác định các bộ giá trị của 4 bàn cờ con ({a
i
, b
i
}, {x
i
, y
i
}) với i = 1 4
call Tromino({a
1
,b
1
}, {x
1
, y
1
}, s);
call Tromino({a
2
,b
2
}, {x
2
, y
2
}, s);
call Tromino({a
3
,b

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

t.assign(1,1,x,y,n);
sTromino.push(t);
d = 0; //dùng để đánh dấu
while (sTromino.isEmpty()==false){
Item_Tromino temp = sTromino.topOfStack();
sTromino.pop();
if(temp.n>1){
int a, b, x, y, d, a1, b1, a2, b2, a3, b3, a4, b4, x1, y1, x2, y2, x3, y3, x4, y4, s;
s = temp.n/2; // s là kích thước của mỗi bàn cờ con
a = temp.a; b = temp.b; x = temp.x; y = temp.y;
//Xác định tọa độ trên bên trái của 4 bàn cờ con
a1 = a; b1 = b;
a2 = a; b2 = b + s ;
a3 = a1 + s; b3 = b1 + s;
a4 = a + s ; b4 = b;
//xác định vị trí đánh dấu của các bàn cờ con
x1 = a + s -1; y1 = b + s -1;
x2 = x1, y2 = y1 + 1;
x3 = x1 + 1; y3 = y2;
x4 = x1 + 1; y4 = y1;
// đánh dấu vào các ô bị đánh dấu ở mỗi bàn cờ con (trừ ô ban đầu)
d++;
if( x< a + s && y< b+ s ) {x1 = x, y1 =y ;M[x2][y2] = M[x3][y3] = M[x4][y4] = d;}
if( x< a + s && y>= b+ s ) {x2 = x, y2 =y ;M[x1][y1] = M[x3][y3] = M[x4][y4] = d;}
if( x>= a + s && y< b+ s ) {x4= x, y4 =y ;M[x1][y1] = M[x2][y2] = M[x3][y3] = d;}
if( x>= a + s && y>= b+ s ) {x3 = x, y3 =y ;M[x1][y1] = M[x2][y2] = M[x4][y4] = d;}
// Lần lượt đưa các tham số ({a
i
, b
i

}{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

, M
l+1
, M
l+2
,…,M
h
chưa có thứ tự
Đầu ra: dãy M
l
, M
l+1
, M
l+2
,…,M
h
có thứ tự không giảm ( M
i
≤M
j
với l≤i<j≤h)
Ý tưởng:
Dựa trên nền tảng thuật toán chia để trị
• Chia:Dãy M
l
, M
l+1
, M
l+2
,…,M
h

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

pos+1
,…,M
h
sẽ được tiếp tục xử lý như
dãy ban đầu cho đến khi mỗi dãy con chỉ còn tối đa 1 phần tử
• Tổ hợp: Do các mảng con được sắp xếp tại chỗ, mỗi lần phân hoạch
phần tử M
pos
nằm đúng vị trí của nó trong dãy, nên sẽ không tốn thời
gian và chi phí để tổ hợp kết quả lại
Xây dựng thuật toán
Thuật toán Phân hoạch dãy M
l
, M
l+1
, M
l+2
,…,M
h
như sau:
Chọn một khoá X=M
k
trong dãy (có thể chọn k=l), dựa vào khoá M để phân hoạch
dãy thành 3 phần như sau:
• Phần 1 chứa các khoá có giá trị <X
.
Các khoá này nằm bên trái của X
trong dãy
• Phần 2 là X
• Phần 3 chứa các khoá có giá trị ≥X

.
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
{

last_small = last_small + i
M
last_small
↔ M
i
}
i ← i+1
}
M
last_small
↔ M
low
Partition = last_small
Return
Như vậy sau khi phân hoạch khoá M
pos
sẽ nằm đúng vị trí của nó khi dãy đã được
sắp xếp xong.
Thuật toán QuickSort được xây dựng như sau
Proc QuickSort(Left, Right) //Left,Right là chỉ số thấp và cao của dãy cần SX
If Left<Right Then
{
Pos ←Partition(Left,Right) //gọi thuật toán Partition
Call QuickSort(Left, Pos-1) //gọi đệ qui cho nửa <M
Pos
Call QuickSort(Pos+1, Right) //gọi đệ qui cho nửa ≥M
Pos
}
Return
Vậy ta dùng 1 stack để lưu trữ 2 chỉ số của cận dưới và cận trên của dãy cần sắp xếp. Chỉ cần

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
}
}
}

}