Sáng kiến kinh nghiệm Ứng dụng thuật toán đệ quy – khử đệ quy trong giảng dạy bồi dưỡng học sinh giỏi

nh(A,low,pivot-1);
 	Sxnhanh(A,pivot+1,hight);
 	}
}
Mã hóa thuật toán
#include
#include
using namespace std;
void swap(int &a, int &b)
{
 int tg = a;
 a = b;
 b = tg;
}
int Chia(int a[], int low, int high)
{
 int pivot = a[high]; // pivot
 int left = low;
 int right = high - 1;
 while(true){
 while(left <= right && a[left] < pivot) left++;
 while(right >= left && a[right] > pivot) right--;
 if (left >= right) break;
 swap(a[left], a[right]);
 left++;
 right--;
 }
 swap(a[left], a[high]);
 return left;
}
void SXNhanh(int a[], int low, int high)
{
 if (low < high)
 {
 /* pi là chỉ số nơi phần tử này đã đứng đúng vị trí và là phần tử chia mảng làm 2 mảng con trái & phải */
 int pi = Chia(a, low, high);
 // Gọi đệ quy sắp xếp 2 mảng con trái và phải
 SXNhanh(a, low, pi - 1);
 SXNhanh(a, pi + 1, high);
 }
}
/* Hàm xuất mảng */
void inmang(int a[], int size)
{
 int i;
 for (i=0; i < size; i++)
 cout<<a[i]<<" ";
 cout<<"\n";
}
int main()
{
 int a[] = {100,10, 80, 30, 20, 40, 50, 70};
 int n = sizeof(a)/sizeof(a[0]);
 SXNhanh(a, 0, n-1);
 cout<<"Sorted array: \n";
 inmang(a, n);
 return 0;
} 
Bài toán tìm kiếm – Thuật toán tìm kiếm nhị phân
Tìm kiếm nhị phân là một trong những phương pháp tìm kiếm phổ biến, một phương pháp tìm kiếm hiệu quả về mặt thời gian và thuật toán dựa trên kỹ thuật chia để trị. 
Phương pháp tìm kiếm nhị phân là phương pháp dùng để tìm kiếm một phần tử trong một mảng gồm n phần tử đã được sắp xếp theo thứ tự (ở đây ta xét trường hợp mảng được sắp theo thứ tự không giảm). 
Phân tích bài toán
Xác định Input, Output:
- Input: Mảng A gồm n phần tử đươc sắp theo thứ tự không giảm. Phần tử cần tìm là x.
- Output: Vị trí của phần tử có giá trị x trong mảng A.
Ý tưởng: Vì mảng đã được sắp theo thứ tự vì vậy ta dựa trên cách tiếp cận chia để trị ta sẽ chia phạm vi tìm kiếm thành hai phần và xác định sẽ tiếp tục tìm kiếm ở phần nào. Quá trình được lặp lại cho đến khi phạm vi tìm kiếm chỉ còn một phần tử và giá trị của phần tử đó bằng giá trị cần tìm hoặc đã tìm đươc phần tử có giá trị bằng giá trị cần tìm . 
Giả sử phạm vi đang tìm kiếm là [d,c], khi dó ta chia mảng thành hai phần có kích thước gần bằng nhau bởi vị trí giữa g. Do tính chất sắp theo thứ tự không giảm của mảng nên ta thấy:
Nếu A[g] = x thì ta dừng thuật toán và thông báo kết quả là g.
Ngược lại, nếu x>A[g] thì phạm vi tìm kiếm tiếp tục sẽ là [g+1,c]. Ngược lại (x<A[g]) thì phạm vi tìm kiếm tiếp tục sẽ là [d,g-1].
Quá trình được lặp lại tương tự cho nửa phạm vị vừa được xác định cho đến khi phạm vi tìm kiếm chỉ còn một phần tử và giá trị của phần tử đó bằng x hoặc đã tìm đươc vị trí của phần tử có giá trị x.
Ví dụ: Cho mảng A đã đươc sắp xếp theo thứ tự không giảm. Tìm vị trí của phần tử x = 57 trong mảng A.
Chỉ số
1
2
3
4
5
6
7
8
Giá trị
6
23
25
34
45
52
57
86

Để tìm x có trong mảng A hay không ta tiến hành các bước như sau:
Bước 1: Chia mảng thành hai phần, với chỉ số giữa g = 4. 
Chỉ số
1
2
3
4
5
6
7
8
Giá trị
6
23
25
34
45
52
57
86

Vì x>A[g], do vậy tiến hành tìm kiếm ở nửa sau của mảng [5,8].
Bước 2: Chia nửa sau của mảng thành hai phần, với chỉ số giữa g = 6.
Chỉ số
5
6
7
8
Giá trị
45
52
57
86

Vì x>A[g], tiến hành tìm kiếm trong phạm vi [7,8].
Bước 3: Tiếp tục chia phạm vi tìm kiếm làm hai phần, với chỉ số giữa g=7.
Chỉ số
7
8
Giá trị
57
86

Vì A[g] = x, do vậy quá trình tìm kiếm kết thúc, chỉ số cần tìm là 7.
Thông số hóa bài toán
Bài toán được khái quát thành bài toán tìm kiếm giá trị x trong một mảng con của mảng A từ chỉ số đầu d đến chỉ số cuối c với 1 <= d <=c <=n. Ta đặt tên cho bài toán dạng tổng quát là TimNhiPhan(A,d,c,x). Bài toán tìm kiếm giá trị x trong mảng A gồm n phần tử sẽ được thực hiện bằng lời gọi TimNhiPhan(A,1,n,x).
Trường hợp neo và thuật toán tương ứng
Khi d>c (n<1) thì ta dừng thuật toán và trả về chỉ số là 0 (x không có trong mảng A) hoặc x có trong mảng A thì dừng thuật toán và lưu lại chỉ số của phần tử có giá trị bằng x.
Phân rã bài toán trong trường hợp tổng quát
Khi d<c ta thực hiện các công việc sau:
Xác định chỉ số của phần tử giữa g = (d+c)/2.
Nếu A[g] = x thì ta dừng thuật toán và thông báo kết quả.
Nếu x>A[g] thì phạm vi tìm kiếm tiếp tục sẽ là [g+1,c].
Ngược lại, nếu x<A[g] thì phạm vi tìm kiếm tiếp tục sẽ là [d,g-1].
Quá trình được lặp lại tương tự cho nửa phạm vị vừa được xác định cho đến khi phạm vi tìm kiếm chỉ còn một phần tử và giá trị của phần tử đó bằng x hoặc đã tìm đươc vị trí của phần tử có giá trị x.
Ta có thể phân rã bài toán TimNhiPhan(A,d,c,x) theo kiểu đệ quy được biểu diển bởi thuật toán sau:
int TimNhiPhan(int A[100],int d,int c,int x)
{
 int g;
 if(d>c) return 0;
 else
 {
 g = (d+c)/ 2;
 if(A[g]==x) TimNhiPhan = g;
 else
 if(A[g]>x)
 TimNhiPhan=TimNhiPhan(A,d,g-1,x);
 else
 TimNhiPhan=TimNhiPhan(A,g+1,c,x);
 }
 }
Mã hóa thuật toán
#include 
using namespace std;
// Hàm tìm kiếm nhị phân sử dụng giải thuật đệ quy
int timNhiPhan(int a[], int d, int c, int x) {
 if (c >= d) {
 int mid = d + (c - d) / 2; // Tương đương (l+r)/2 nhưng ưu điểm tránh tràn số khi l,r lớn
 // Nếu arr[mid] = x, trả về chỉ số và kết thúc.
 if (a[mid] == x)
 return mid;
 // Nếu arr[mid] > x, thực hiện tìm kiếm nửa trái của mảng
 if (a[mid] > x)
 return timNhiPhan(a, d, mid - 1, x);
 // Nếu arr[mid] < x, thực hiện tìm kiếm nửa phải của mảng
 return timNhiPhan(a, mid + 1, c, x);
 }
 // Nếu không tìm thấy
 return -1;
}
int main(void) {
 int a[] = {2, 3, 4, 10, 40};
 int n = sizeof(a) / sizeof(a[0]);
 int x = 4;
 int result = timNhiPhan(a, 0, n - 1, x);
 if (result == -1)
 cout<<x<<"xuat hien tai chi so"<< result;
 else
 cout<<x<<"xuat hien tai chi so"<<result;
 return 0;
}
2. KỸ THUẬT KHỬ ĐỆ QUY
2.1. Lý do sử dụng kỹ thuật khử đệ quy 
Trong việc thực hiện chương trình con đệ quy, mỗi lần gọi chương trình con đệ quy sẽ tạo ra một tập các biến cục bộ. Nếu chúng ta chủ động quản lý các giá trị trung gian này bằng ngăn xếp (Stack) và thay các lời gọi đệ quy bằng các vòng lặp thì chúng ta sẽ thu được một chương trình tương đương không có lời gọi đệ quy. Việc làm nói trên được gọi là khử đệ quy. Hay nói khác đi, khử đệ quy là bỏ đi các lời gọi đệ quy và thay vào đó là việc sử dụng cơ chế lặp cùng với sự hỗ trợ của ngăn xếp. Việc gọi đệ quy trong nhiều trường hợp dẫn tới việc tính lại nhiều lần cùng một giá trị, gây lãng phí về mặt thời gian. Trong khi đó, các thuật toán khử đệ quy có thể chủ động quản lý các tài nguyên của máy, ta có thể chủ động đưa ra các thông báo hợp lý trong chương trình khi xảy ra các biến cố như tràn vùng nhớ. Không những thế, một số chương trình khử đệ quy cũng ngắn gọn và tối ưu không kém gì các chương trình đệ quy.
Vì vậy, việc thay thế một chương trình đệ quy (có chứa chương trình con đệ quy) bằng một chương trình không đệ quy là một vấn đề cần thiết và được quan tâm nhiều trong lập trình. Tuy nhiên do việc khử đệ quy không phải bao giờ cũng làm được vì vậy trong nhiều trường hợp ta phải chấp nhận sử dụng chương trình đệ quy. 
2.2. Một số kỹ thuật khử đệ quy đơn giản 
Việc viết các chương trình khử đệ quy phải thêm vào các thao tác quản lý các giá trị tính toán trung gian để phục vụ cho các phép quay lui dẫn tới kết quả cuối cùng của chương trình. Khi đó, chúng ta sử dụng ngăn xếp để lưu trữ các giá trị trung gian này.
2.3. Khử một số dạng đệ quy thường gặp
2.3.1. Khử đệ quy dạng ED [AP]
Xét thuật toán đệ quy P(x) dạng sau:
P(x) {if (E(x)) D(x)
 else 
 {
 A(x);
 P(f(x));
 }
 }
Trong đó: 
x : là tập biến (một hoặc một bộ nhiều biến). Trong trường hợp tổng quát x là một dãy các biến x1, x2, x3, , xn thuộc các kiểu dữ liệu khác nhau.
P(x): là một thuật toán đệ quy với danh sách tham số hình thức x.
E(x): là điều kiện kết thúc đệ quy cho thuật toán.
D(x), A(x): là các nhóm thao tác (lệnh) không đệ quy.
f(x): là một hàm biến đổi một hoặc tất cả các thành phần của tập x.
Xét quá trình thi hành P(x):
- Gọi P0 là lần gọi P thứ 0 (đầu tiên) 	P(x)
- P1 là lần gọi P thứ 1 (lần 2)	P(f(x))
- Pi là lần gọi P thứ i (lần i+1)	P(f(f(f(x))
	(P(fi(x) là hợp i lần hàm f) 
Trong lần gọi Pi nếu E(fi(x)) đúng (true) thì thi hành lệnh D và kết thúc quá trình. Ngược lại, nếu E(fi(x)) không đúng (false) thì thi hành lệnh A và gọi Pi+1. 
Đặt x = f(x) và dựa vào quá trình thi hành P(x) ta thấy nó có tính chất của một quá trình lặp. Từ đó, ta có sơ đồ khối tương ứng như sau:
D(x)
A(x)
E(x)
x = f(x)
true
false
Hình 2. Sơ đồ khối thực hiện thuật toán đệ quy P(x)
Và do đó thuật toán đệ quy dạng (1) được chuyển thành vòng lặp, hay nói cách khác dạng không đệ quy tương ứng của (1) sẽ là:
P(x) { while (! E(x))
 {
 A(x);
 x = f(x);
 }
 D(x);}
Ví dụ: Bài toán tìm ước số chung lớn nhất của 2 số nguyên dương dựa vào thuật toán Euclid.
Thuật toán đệ quy tìm ước số chung lớn nhất bằng thuật toán Euclid như sau:
USCLN(m, n, us) { if (n == 0) us = n;
 else 
 USCLN(n,m % n,us); }
Trong trường hợp này thì: 
x là (m, n).
P(x) là USCLN(m, n).
E(x) là biểu thức logic (n == 0).
D(x) là lệnh gán us = n.
A(x) là lệnh rỗng.
f(x) là f(m, n, us) = (n, m % n, us).
Áp dụng cho thuật toán tìm ước số chung lớn nhất của hai số m, n ta có:
USCLN(m, n, us) { while (n != 0) 
 {
 	tg = m % n;
 	 	m = n;
	 	n = tg;
	 	}
	 us = n; } 
2.3.2. Khử đệ quy dạng ED [APB]
Thuật toán P(x) có dạng ED [APB] được mô tả như sau:
P(x) {if(E(x)) D(x) 
 else 
 {
 	A(x);
 	P(f(x));
 	B(x);
 } }
Trong đó:
Các thành phần A(x), B(x) và D(x) là các nhóm lệnh không đệ quy.
E(x) là điều kiện kết thúc đệ quy.
Ví dụ: Thuật toán đệ quy chuyển biểu diễn số từ cơ số thập phân sang nhị phân:
Chuyencoso(m) {if (m>0) 
	{
 Chuyencoso(m / 2);
 cout<<m % 2;
 } }
 Trong trường hợp này:
x là m.
E(x) là (m<=0).
P(x) là Chuyencoso(m).
A(x), D(x) là lệnh rỗng.
B(x) là lệnh cout<<m % 2.
f(x) = f(m) = m / 2.
Ta nhận thấy rằng chừng nào P(f(x)) chưa kết thúc thì toán tử B(x) chưa được thực hiện. Để khử đệ quy cho dạng này ta phải tìm cách cất giữ các giá trị của x, f(x), f(f(x))v.v. Cho đến khi nào điều kiện E(x) trở thành đúng. Sau đó, ta thực hiện D(x) và lần lượt lấy các giá trị x đã cất giữ ra để thực hiện toán tử B(x).
Nếu thành phần P của đệ quy kết thúc sau k+1 lần lặp, tức là nếu E(fk(x)) nhận giá trị đúng (true) với fk(x) = fff(x) và f0(x) = x thì sau khi thực hiện D(fk(x)) ta sẽ phải thực hiện B(fk(x)) và do đó kết thúc thành phần P của đệ quy cho k lần lặp, tiếp đó ta sẽ phải thực hiện toán tử B(fk(x)), B(fk-1( x)), ..v.v.., cuối cùng là B(x). Tóm lại, tham trị của B sẽ phải được cất giữ thành chồng rồi lấy ra theo chiều từ trên xuống. Ngăn xếp được sử dụng vào chính mục đích này. Với ngăn xếp S chứa các phần tử có kiểu dữ liệu phù hợp với kiểu của x.
Trình tự thực hiện P(x) được diễn tả bằng mô hình sau:
P(x)
E(x) = false
A(x)
Push(S,x); u=f(x); P(u);
Pop(S,u);B(u);
 (u=x)
E(u) = false
A(u)
Push(S,u); u=f(u); P(u);
Pop(S,u);B(u);
 (u=f(x))
E(u) = false
A(u)
Push(S,u); u=f(u); P(u);
Pop(S,u);B(u);
 (u=f(x))
..
E(u) = false
A(u)
Push(S,u); u=f(u); P(u);
Pop(S,u);B(u);
 (u=f(x))
E(u) = true
D(u)
Thuật toán không đệ quy cho dạng (2) với việc sử dụng ngăn xếp Stack như sau:
P(x) { Khoitao(S);
 While (!(E(x)) 
 {
 A(x);
 push(S,x);
 x = f(x);
 }
 D(x);
 while (!(rong(S))) 
 {
 pop(S, x);
 B(x);
 }
 }
Áp dụng cho thuật toán chuyển biểu diễn số từ cơ số thập phân sang nhị phân:
Chuyencoso(m) = { Khoitao(S);
 while( m>0) 
	 { sodu = m % 2;
 push(S, sodu);
 m = m / 2;
 }
 while (!(rong(S))) 
	 {
 pop(S,sodu);
 cout<<sodu;
 }
2.4. Nhận xét chung về kỹ thuật khử đệ quy
Các kỹ thuật khử đệ quy đã trình bày ở trên mới chỉ áp dụng được cho một số thuật toán đệ quy trực tiếp. Nhìn chung, mọi thuật toán đệ quy trực tiếp đều tồn tại lời giải không đệ quy của nó. Các thuật toán đệ quy gián tiếp cho đến nay vẫn chưa có phương pháp tổng quát để khử đệ quy.
Với các kỹ thuật khử đệ quy nêu trên ta thấy thuật toán khử đệ quy hoàn toàn tương đương với các dạng đệ quy của chúng. Ở đây sự tương đương được so sánh về phương diện kết quả đầu ra và thời gian tính toán của thuật toán. Về thực chất trong chương trình khử đệ quy chúng ta đã làm thay đổi một số phần việc của chương trình dịch khi tổ chức lưu trữ dữ liệu trong ngăn xếp. Do đó, với các chương trình đã được khử đệ quy thì ta có thể kiểm soát được tài nguyên vùng nhớ, đồng thời có thể đưa ra được các thông báo hợp lý khi tài nguyên vùng nhớ bị cạn kiệt . 
PHẦN III. KẾT LUẬN VÀ KIẾN NGHỊ
I. KẾT LUẬN
Bồi dưỡng học sinh giỏi là nhiệm vụ hết sức khó khăn và nặng nề với giáo viên, đòi hỏi giáo viên phải có lòng đam mê và nhiệt tình, có tinh thần trách nhiệm với học sinh. Lấy tinh thần đam mê để làm động lực phấn đấu. Qua thời gian tìm hiểu. Tôi đã đạt được một số kết quả như đã tìm hiểu về thuật toán đệ quy, cách hoạt động của chương trình đệ quy, cách viết các chương trình đệ quy  Bên cạnh đó, tôi cũng đã tìm hiểu về các kỹ thuật khử đệ quy cho một số dạng thuật toán đệ quy thường gặp và ứng dụng để khử một số bài toán thuộc dạng đệ quy. Hy vọng với chuyên đề này, sẽ góp phần cổ vũ, động viên tinh thần và chia sẻ khó khăn với những giáo viên làm công tác bồi dưỡng học sinh giỏi.
Bồi dưỡng học sinh giỏi hiện nay rất được quan tâm, chú trọng ở các trường phổ thông, sở giáo dục và đặc biệt nhất đây là nhiệm vụ hết sức quan trọng đối với các tổ chuyên môn. Chuyên đề này giúp cho các em học sinh có thể vận dụng giải quyết các bài toán đệ quy- khử đệ quy, giúp các em lĩnh hội kiến thức và góp phần nâng cao hiệu quả giải các dạng bài toán này. Ngoài ra, cũng có thể giúp cho giáo viên có thêm tài liệu tham khảo khi dạy bồi dưỡng học sinh giỏi.
Chuyên đề này được đúc rút mới chỉ là ý tưởng chủ quan của cá nhân, chắc hẳn vẫn còn nhiều thiếu sót, mong được sự đóng góp của các bạn đồng nghiệp.
II. KIẾN NGHỊ
Qua đề tài này, tôi mong muốn tìm tòi và học hỏi nhiều hơn nữa các lớp bồi dưỡng với chuyên đề “Ôn tập bồi dưỡng học sinh giỏi” cho giáo viên các trường trên địa bàn và triệu tập những giáo viên có kinh nghiệm về bồi dưỡng học sinh giỏi biên soạn tài liệu về “Phương pháp bồi dưỡng học sinh giỏi môn Tin học” cung cấp cho các trường làm tài liệu bồi dưỡng để đạt kết quả cao nhất.
XÁC NHẬN CỦA HIỆU TRƯỞNG
Hướng Hóa, ngày 8 tháng 7 năm 2020
Tôi xin cam đoan đây là SKKN của mình viết, không sao chép nội dung của người khác.
Người viết
Nguyễn Tiến Long

TÀI LIỆU THAM KHẢO
Dương Trần Đức (2007). Giáo trình cấu trúc dữ liệu và giải thuật. Hà Nội: nhà xuất bản Trung tâm đào tạo bưu chính viễn thông 1.
Trần Hoàng Thọ (2002). Giáo trình kỹ thuật lập trình nâng cao. Đà Lạt: nhà xuất bản Đại học Đà Lạt.
Nguyễn Xuân Huy (1988). Thuật toán. Hà Nội: nhà xuất bản thống kê.
Lê Minh Hoàng, 2006. Bài giảng chuyên đề, NXB Đại học sư phạm
Hồ Anh Minh (2003), Giáo trình nhập môn thuật toán. Quy Nhơn: nhà xuất bản Đại học Quy Nhơn.