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

hóm thứ nhất không dành cho học sinh xếp cuối cùng phần thưởng nào cả (Sn = 0). Số cách chia này sẽ bằng số cách chia m phần thưởng cho n-1 học sinh. Khi đó, số cách chia trong nhóm thứ nhất bằng hàm Chiathuong(m,n-1).
Nhóm thứ hai có phần thưởng cho người cuối cùng (Sn > 0). Dễ thấy rằng số cách chia của nhóm này bằng số cách chia m-n phần thưởng cho n học sinh (vì phương thức chia mà tất cả học sinh đều nhận được phần thưởng có thể thực hiện bằng cách cho mỗi người nhận trước một phần thưởng rồi mới chia). Khi đó, số cách chia trong nhóm thứ hai bằng hàm Chiathuong(m-n,n). 
Vậy khi mn: Chiathuong(m,n) = Chiathuong(m,n-1) + Chiathuong(m-n,n).
Mã hóa thuật toán
#include
using namespace std;
int Chiathuong(int m,int n)
 {
 if ((m==0)||(n==1)) return 1;
 else
 	if (m<n) return Chiathuong(m,m);
 	else
 	return Chiathuong(m,n-1)+Chiathuong(m-n,n);
 }
 int main(){
 cout<<"chia thuong "<<Chiathuong(2,7);
 	return 0;
 }
Bài toán sắp xếp mảng – Thuật toán sắp xếp nhanh
Sắp xếp là một bài toán thường gặp, ngoài ý nghĩa tổ chức lại dữ liệu theo một yêu cầu nào đó, việc sắp xếp còn tạo thuận lợi cho việc tìm kiếm. Có nhiều phương pháp sắp xếp khác nhau, trong đó Quicksort là một phương pháp sắp xếp được nghiên cứu và sử dụng rộng rãi trong lớp các thuật toán sắp xếp.
Các đối tượng dữ liệu cần sắp xếp thường có nhiều thuộc tính, về cấu trúc dữ liệu được tổ chức khá đa dạng, và ta cần chọn một khóa để sắp xếp dữ liệu theo khóa này. Ví dụ như mô tả đối tượng con người có các thuộc tính cơ bản như họ tên, ngày sinh, giới tính, v.v.., và thuộc tính họ tên được chọn làm khóa để sắp xếp. Tuy nhiên, để thuận lợi cho việc trình bày cũng như tập trung vào thuật toán ta sẽ làm việc với mảng đơn giản gồm các số nguyên.
Đối với các bài toán sắp xếp được xét ở đây chúng ta sẽ quan tâm tới việc sắp xếp mảng các số nguyên theo thứ tự không giảm.
Phân tích bài toán
Xác định Input, Output:
Input: mảng số nguyên gồm n phần tử
Output: mảng số nguyên được sắp xếp theo thứ tự không giảm.
Ý tưởng cơ bản của Quicksort dựa trên phương pháp chia để trị và được mô tả dưới dạng đệ quy. Đầu tiên chọn một phần tử trong mảng làm mốc, sau đó chia mảng thành hai phần ở hai phía của mốc: các phần tử lớn hơn mốc được chuyển sang phải mốc và các phần tử không lớn hơn mốc được chuyển sang trái mốc. Để có được sự phân chia này, các phần tử sẽ được so sánh với mốc và hoán đổi vị trí cho nhau hoặc cho mốc nếu nó lớn hơn mốc mà lại nằm bên trái hoặc không lớn hơn mốc mà lại nằm bên phải. Áp dụng kỹ thuật trên cho hai phần vừa được chia và tiếp tục thực hiện như vậy cho đến khi mỗi mảng con chỉ còn một phần tử. Khi đó toàn bộ mảng đã được sắp xếp không giảm.
Giả sử để chia mảng A[d..c] thành hai phần thỏa mãn yêu cầu trên. Ta tiến hành các bước cụ thể như sau:
 - Lấy một phần tử trong mảng làm mốc. Ở đây ta sẽ chọn phần tử đầu tiên của mảng làm mốc là A[d].
 - Tiến hành duyệt mảng A đồng thời từ hai đầu, dùng hai biến i, j để duy trì hai vị trí duyệt. Khởi tạo i = d+1 và j = c. Duyệt từ bên trái mảng và tăng i cho tới khi gặp một phần tử có giá trị lớn hơn mốc (A[i]>A[d]), đồng thời tiến hành duyệt từ bên phải sang và giảm j cho tới khi gặp một phần tử có giá trị nhỏ hơn hoặc bằng mốc (A[j]A[d]). Rõ ràng hai phần tử này nằm ở những vị trí không phù hợp khi đó đổi chỗ A[i] và A[j]. Quá trình này còn tiếp tục khi nào mà i<j. Cuối cùng đổi chỗ A[d] và A[j] để đặt mốc đúng chỗ.
Ví dụ: Cho mảng A gồm 5 phần tử sau:
Chỉ số
1
2
3
4
5
6
7
Giá trị
15
6
18
1
12
24
49
Chọn mốc: A[1] = 15; biến duyệt ban đầu: i = 2, j = 7.
Quá trình duyệt từ bên trái với biến i sẽ dừng lại tại phần tử thứ 3, A[3]=18, vì đây là phần tử có giá trị lớn hơn mốc.
Quá trình duyệt từ bên phải với biến j sẽ dừng lại tại phần tử thứ 5, A[5]=12, vì đây là phần tử có giá trị nhỏ hơn mốc. 
Chỉ số
1
2
3
4
5
6
7
Giá trị
15
6
18
1
12
24
49
i
j
Vì i<j nên ta đổi chỗ (A[i],A[j]) thu được mảng A có giá trị sau:
Chỉ số
1
2
3
4
5
6
7
Giá trị
15
6
12
1
18
24
49
i
j
Tiếp tục quá trình duyệt, hai biến i, j gặp nhau (i = j) quá trình duyệt dừng lại, cuối cùng ta đổi chỗ (A[1],A[j]), khi đó mảng A được phân thành hai nữa như sau:
Chỉ số
1
2
3
4
5
6
7
Giá trị
1
6
12
15
18
24
49
Thông số hóa bài toán
Ta gọi thuật toán giải bài toán ở mức tổng quát là thủ tục SXnhanh(A[n], d, c), sắp xếp mảng A gồm n ứng với chỉ số đầu d và chỉ số cuối c theo thứ tự không giảm. Trong đó, n thuộc kiểu số nguyên và n chính là thông số quyết định độ phức tạp của bài toán. 
Trường hợp neo và thuật toán tương ứng
Khi d = c, thuật toán sẽ dừng lại và hoàn tất việc sắp xếp.
Phân rã bài toán trong trường hợp tổng quát
Ta có thể phân rã bài toán SXnhanh(A[n],d,c) theo kiểu đệ quy được biểu diễn bởi thuật toán sau:
void SXnhanh(int A[100],int low,int hight)
{
int pivot;
 	if (low<hight)
 	{
 	pivot = Chia(A,low,hight); //chia mảng A thành hai phần
 	Sxnhanh(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.