SKKN Một số kinh nghiệm giải toán bằng phương pháp đệ quy trong ôn thi học sinh giỏi

MỤC LỤC
A. PHẦN MỞ ĐẦU 	2
I. Lý do chọn đề tài: 	2
II. Mục đích nghiên cứu: 	3
III. Đối tượng và phạm vi nghiên cứu: 	3
IV. Nhiệm vụ nghiên cứu: 	3
V. Phương pháp nghiên cứu: 	4
B. PHẦN NỘI DUNG 	5
I. Cơ sở lý luận của đề tài: 	5
1. Các khái niệm: 	5
a) Khái niệm Đệ quy: 	5
b) Đặc điểm của chương trình con đệ quy:	6
c) Phân loại đệ quy: Gồm 2 loại: 	6
2. Nguyên tắc hoạt động của giải thuật đệ quy: 	7
a) Khái niệm stack: 	7
b) Nguyên tắc hoạt động của giải thuật đệ quy ứng dụng Stack: 	7
c) Ưu điểm và nhược điểm của giải thuật đệ quy: 	8
3. Đệ quy quay lui: 	8
a) Khái niệm đệ quy quay lui: 	8
b) Giải thuật tổng quát của đệ quy quay lui: 	9
c) Nét đặc trưng của phương pháp đệ quy quay lui: 	10
d) Ưu và nhược điểm: 	11
4. Phương pháp khử đệ quy: 	11
5. Sự khác nhau giữa đệ quy và lặp: 	12
II. GIẢI PHÁP NÂNG CAO HIỆU QUẢ ÔN LUYỆN THI HSG THÔNG QUA CÁC BÀI TẬP VÍ DỤ ĐỆ QUY, ĐỆ QUY QUAY LUI VÀ KHỬ ĐỆ QUY. 	13
1. Các bài tập cơ bản về đệ quy và không đệ quy: 	13
2. Các bài tập đệ quy và đệ quy quay lui: 	14
3. Kết quả đạt được: 	19
C. KẾT LUẬN VÀ KIẾN NGHỊ 	20
A. PHẦN MỞ ĐẦU
I. Lý do chọn đề tài:
	Như chúng ta đã biết, việc đào tạo bồi dưỡng học sinh giỏi thật sự là công việc rất khó khăn, đòi hỏi nhiều công sức của giáo viên và học sinh. Trong một những năm gần đây, trong các kỳ thi chọn học sinh giỏi các môn văn hóa cấp tỉnh, đội tuyển học sinh giỏi trường THPT Nông Cống 4 đã đạt được rất nhiều thành tích cao, cụ thể xếp hạng trong các năm học từ 2015 trở về trước đứng dưới thứ 40 của tỉnh. Trong năm học 2016-2017 vượt lên thứ 28 và năm học 2017-2018 giữ nguyên thứ hạng. Điều này được sự góp phần công sức rất lớn lao của đội ngũ các thầy cô trực tiếp giảng dạy, sự vươn lên mọi khó khăn từ các em học sinh đã góp phần vào kết quả chung của nhà trường, trong đó có sự đóng góp thành tích của bộ môn Tin học. Vì vậy bản thân tôi luôn cố gắng phấn đấu để cùng bắt nhịp với đội tuyển các môn trong nhà trường.
	Tuy nhiên, sau nhiều năm đào tạo, tôi nhận thấy thực trạng của công tác ôn thi học sinh giỏi của bộ môn Tin học đã bộc lộ những khó khăn và thuận lợi sau:
	+ Thuận lợi:
          - Được sự quan tâm, động viên của Ban giám hiệu nhà trường. Sự đồng lòng của các bậc phụ huynh học sinh trong đội tuyển đã động viên và dành thời gian để các em ôn luyện.
	 - Sự đúc kết kinh nghiệm giảng dạy, trau dồi kiến thức của bản thân trong quá trình giảng dạy.
	 - Học sinh có ý thức học tập, say mê trong môn học nặng về tư duy, trong đó năm học 2017-2018 đã có 2 em trong đội tuyển Tin học thi 2 môn: 1 em thi môn Hóa và 1 em thi môn Toán.
	+ Khó khăn:
          - Tìm kiếm và xây dựng nguồn nhân lực rất khó khăn, nhất là trong điều kiện mà bắt đầu từ năm học 2017-2018 khối học sinh 12 không tham gia dự thi, điều này đã làm cho lực lượng học sinh có chất lượng khối 11 khó có thể thi Tin học (vì các em học môn tự nhiên đã thi môn khác).
 - Học sinh luôn đứng trước sự lựa chọn giữa học chuyên sâu để thi học sinh giỏi và học để thi ĐH-CĐ, dẫn đến việc thi môn trái với môn thi ĐH-CĐ là không nằm trong sự lựa chọn của các em.
 - Một số học sinh tham gia học bồi dưỡng nhưng chưa thật cố gắng nên kết quả thi học sinh giỏi chưa cao.	
	 - Bản thân chưa đủ điều kiện, thời gian để tự bồi dưỡng, nghiên cứu nhằm nâng cao chất lượng dạy học, trong khi đó áp lực công việc ôn luyện không hề nhỏ.
         - Cơ sở vật chất, trang thiết bị, tài liệu dạy học phục vụ cho công tác bồi dưỡng HSG còn nhiều thiếu thốn, hư hỏng nhiều.
	 - Đặc biệt khối kiến thức thi học sinh giỏi rất rộng, trong khi đó các em chỉ được ôn luyện từ khi làm quen với ngôn ngữ lập trình cho đến khi đi thi chỉ được khoảng 2-3 tháng.
          Trước những thuận lợi và khó khăn như trên và qua nhiều năm tham gia ôn luyện thi học sinh giỏi tôi đã rút ra nhiều bài học kinh nghiệm, trong đó có việc giúp học sinh đạt kết quả cao nhất của những bài thi khó, đó là các bài cuối cùng của đề thi. Những dạng bài này thường dùng giải thuật đệ quy để giải. 
	Như ta đã biết, các phép lặp là một trong những kỹ thuật được dùng để giải các bài toán bằng cách thực hiện liên tiếp một số các câu lệnh trong vòng lặp cho tới khi một điều kiện nào đó được thỏa mãn. Một kỹ thuật lập trình được sử dụng để thay thế cho các phép lặp đó là kỹ thuật đệ quy. Mặt khác, trong thực tế có rất nhiều bài toán đòi hỏi sự lặp đi lặp lại một cách phức tạp. Và đệ quy cung cấp cho ta cơ chế giải quyết bài toán phức tạp một cách đơn giản. Hơn nữa, đệ quy còn thích hợp để giải quyết các bài toán có bản chất đệ quy và rất nhiều bài toán cho đến nay vẫn chưa có lời giải phi đệ quy. 
	Từ mục đích nhằm nâng cao kết quả ôn luyện thi học sinh giỏi, đồng thời giải quyết các khó khăn trong quá trình ôn luyện tôi đã chọn đề tài “Một số kinh nghiệm nâng cao hiệu quả ôn thi học sinh giỏi thông qua các bài toán đệ quy, khử đệ quy và đệ quy quay lui” làm đề tài sáng kiến kinh nghiệm của mình.
II. Mục đích nghiên cứu:
	- Nhằm nâng cao hiệu quả ôn luyện thi học sinh giỏi.
	- Gây hứng thú đối với học sinh tham gia thi học sinh giỏi môn tin học thông qua việc sinh test cho mỗi bài tập để chấm điểm, phân tích dữ liệu xử lý.
	- Khắc phục các khó khăn khi giải các bài toán khó trong đề thi.
	- Nâng cao năng lực của bản thân cũng như các đối tượng có sử dụng phương pháp đệ quy để giải bài tập.
III. Đối tượng và phạm vi nghiên cứu:
1. Đối tượng:
	Đối tượng nghiên cứu của đề tài là tìm hiểu về lý thuyết đệ quy, xây dựng các phương pháp giải đệ quy thông qua các bài tập từ đơn giản đến phức tạp.
2. Phạm vi:
	- Thực hiện các giải các bài toán bằng phương pháp đệ quy. 
IV. Nhiệm vụ nghiên cứu:
	- Nghiên cứu những cơ sở về lý luận về lý thuyết đệ quy, tìm hiểu các ứng dụng về đệ quy.
	- Nghiên cứu và phân tích các đặc điểm, ưu - nhược điểm khi sử dụng giải toán bằng phương pháp đệ quy. 
	- Nghiên cứu thực tiễn dạy học trong quá trình hướng dẫn học sinh giải toán bằng đệ quy. 
V. Phương pháp nghiên cứu:
1. Lý thuyết
	- Tham khảo tài liệu sách, báo, mạng Internet có liên quan trực tiếp đến đề tài.
2. Thực tiễn
Trong quá trình dạy học ôn luyện thi học sinh giỏi lần lượt thực hiện các bước sau:
	+ Tìm hiểu lý thuyết, các bài toán nào ứng dụng bằng phương pháp đệ quy.
	+ Xây dựng các bài toán đơn giản giải bằng phương pháp đệ quy để học sinh tiếp cận từng bước các dạng toán được áp dụng.
	+ Thực hiện giải các bài toán khó trong đề thi HSG tỉnh các năm và đề thi các tỉnh khác.
	+ Tạo các TEST cho mỗi bài tập từ bài dễ đến khó nhằm tạo hứng thú học tập cho học sinh, đồng thời đánh giá được độ phức tạp của thuật toán, đánh giá được năng lực phân tích thuật toán để viết được một chương trình tối ưu nhất.
B. PHẦN NỘI DUNG
I. Cơ sở lý luận của đề tài:
1. Các khái niệm:
a) Khái niệm Đệ quy: 
          Nếu thuật toán của một bài toán A được thực hiện bằng thuật toán của bài toán A’ có dạng giống như A, thì đó là thuật toán đệ quy. (A’ nhỏ hơn A). Hay có thể nói cách khác đó là: Từ bài toán A chúng ta có thể chia nhỏ bài toán đó thành các bài toán con cùng kiểu so với bài toán gốc ban đầu, cứ chia nhỏ như vậy cho đến khi nào gặp đến bài toán cơ bản nhất mà chúng ta có thể xử lý được (trường hợp suy biến) thì thao tác dừng.
          Như vậy trong quá trình lập trình, việc xây dựng các chương trình con (thủ tục/hàm) nếu sử dụng phương pháp đệ quy sẽ được hiểu như sau: Chương trình con đệ quy là chương trình con mà trong đó có lời gọi tới chính chương trình con đó.
+ Các bài toán có thể dùng đệ quy:
	Bài toán dễ dàng giải quyết trong một số trường hợp riêng ứng với các giá trị đặc biệt của tham số. Ta gọi đây là trường hợp suy biến. Trong trường hợp tổng quát, bài toán có thể quy về một bài toán cùng dạng nhưng giá trị tham số thì bị thay đổi. Và sau một số hữu hạn bước biến đổi Ðệ Quy sẽ dẫn đến trường hợp suy biến.
Ví dụ: 
+ Kết quả với test n = 5:
	5! 	= 5 x 4!
	= 5 x (4 x 3!)
	= 5 x (4 x (3 x 2!))
	= 5 x (4 x (3 x (2 x 1!)))
	= 5 x (4 x (3 x (2 x (1 x 0!)))) àTrường hợp suy biến
	= 5 x (4 x (3 x (2 x 1)))
	= 120.
 1. Định nghĩa về giai thừa n!: 
	 0! = 1 
	 Nếu n>0 thì n!=n*(n-1)! 
+ Code mô tả như sau:
Function gt(n: Word): Longint; 
 Begin 
 If n = 0 then gt : =1 
 Else gt := n*gt(n - 1); 
 End; 
Các bài toán khác:
 	2. Định nghĩa về số tự nhiên: 
	 0 là một số tự nhiên 
	 n là một số tự nhiên khi n-1 là 1 số tự nhiên 
 3. Định nghĩa dãy Fibonacci f(n):
	 1,	Nếu n = 1; 
	 1, 	 	 Nếu n = 2;
	 F(n-1) + f(n-2) Nếu n > 2. 
	Từ các ví dụ trên chúng ta nhận thấy chúng đều có chung cấu trúc dạng hàm gọi các hàm khác dưới dạng mô hình phân cấp. Tuy nhiên đối với một số bài toán, việc dùng hàm gọi ngay chính nó rất hữu dụng. Có thể định nghĩa hàm đệ quy là hàm sẽ gọi đến chính nó trực tiếp hay gián tiếp thông qua các hàm khác. Vấn đề đệ quy là một vấn đề rất phức tạp, gây khó hiểu cho người học, đặc biệt là những học sinh mới học lập trình có tư duy thuật toán chưa sâu. Do đó trong đề tài sẽ giới thiệu, phân tích, mô phỏng các bài toán đệ quy từ đơn giản đến phức tạp để các em dễ dàng tiếp cận.
	Trước tiên ta xem xét khái niệm đệ quy, sau đó kiểm tra trên một vài chương trình có chứa các hàm đệ quy. Cách tiến hành giải một bài toán đệ quy nhìn chung có những điểm chung sau.
	Trước tiên gọi hàm đệ quy để giải bài toán, hàm đệ quy thực ra chỉ biết cách giải bài toán trong trường hợp đơn giản nhất (hay còn gọi là trường hợp cơ sở). Nếu hàm đệ quy được gọi trong trường hợp cơ sở, hàm chỉ cần đơn giản trả lại kết quả. Nếu hàm được gọi trong các trường hợp phức tạp hơn, hàm đệ quy sẽ chia công việc cần giải quyết thành hai phần. Một phần hàm biết cách giải quyết như thế nào, còn phần kia vẫn không biết cách giải quyết như thế nào tuy nhiên để được gọi là có khả năng đệ quy, phần sau phải giống với bài toán ban đầu nhưng đơn giản hơn hay nhỏ hơn bài toán ban đầu. Bởi vì bài toán mới giống với bài toán ban đầu nên hàm sẽ thực hiện gọi chính nó để giải quyết công việc đơn giản hơn này - đây chính là lời gọi đệ quy hay còn gọi là một bước đệ quy. Ðể đảm bảo việc đệ quy có kết thúc, mỗi một lần gọi đệ quy thì bài toán phải đảm bảo đơn giản hơn và các bước đệ quy này còn thực hiện tiếp cho đến khi nào bài toán đơn giản dần, đơn giản tới mức trở thành trường hợp cơ sở. Có thể nhận thấy hàm đệ quy xử lý trường hợp cơ sở để trả lại kết quả tính được cho các hàm mức phức tạp hơn, rồi đến lượt các hàm này lại tính trả lại kết quả cho các hàm phức tạp hơn nữa ... cứ như vậy cho đến lời gọi hàm ban đầu.
b) Đặc điểm của chương trình con đệ quy:
          - Trong chương trình con đệ quy có lời gọi đến chính chương trình con đó.
          - Mỗi lần gọi lại chương trình con đó thì kích thước bài toán đã thu nhỏ hơn trước.
          - Có một trường hợp đặc biệt: đó là trường hợp suy biến. Đây chính là trường hợp giúp chúng ta kết thúc việc chia nhỏ chương trình để từ đây truy hồi công thức lấy kết quả.
c) Phân loại đệ quy: Gồm 2 loại: 
Đệ quy trực tiếp và Đệ quy gián tiếp.
+ Đệ quy trực tiếp: Là loại đệ quy mà đối tượng được mô tả trực tiếp qua nó: 
	Ví dụ 1: A mô tả qua A, B, C Trong đó B, C không chứa A. 
	Ví dụ 2: Mô tả đệ quy cây gia phả: Gia phả của một người bao gồm người đó và gia phả của người ch và gia phả của người mẹ.
	Ví dụ 3: Mô tả đệ quy về thi chọn hoa hậu: 
Chọn hoa hậu của từng khu vực.
Chọn hoa hậu của các hoa hậu.
	+ Đệ quy gián tiếp: Là loại đệ quy mà đối tượng được mô tả gián tiếp qua nó: 
	Ví dụ: A mô tả qua B, C, D. Trong đó: B được mô tả qua A và E, còn C và D không chứa A
2. Nguyên tắc hoạt động của giải thuật đệ quy:
Hình ảnh minh họa hoạt động của stack
	Trong quá trình thực hiện lời gọi đệ quy, các tham số, biến cục bộ hay địa chỉ sẽ được lưu tạm thời trong bộ nhớ. Các giá trị trên sẽ được lấy ra để giải quyết khi xảy ra trường hợp suy biến, giá trị vào sau cùng sẽ được lấy ra đầu tiên. Chính vì vậy quá trình lưu và xử lý dữ liệu sẽ thực hiện theo mô hình stack.
a) Khái niệm stack: 
	Stack (ngăn xếp) là một danh sách mà việc thêm và xóa các phần tử chỉ diễn ra ở một đầu của danh sách. Stack được thiết kế theo nguyên lý Last-In-First-Out (LIFO), nghĩa là vào sau, ra trước. Phần tử nào được thêm vào sau cùng sẽ là phần tử được lấy ra đầu tiên.
Ví dụ: - Xếp đĩa CD chồng lên nhau, đĩa CD cuối cùng đưa vào sẽ là đĩa CD đầu tiên lấy ra
+ Đặc điểm của Stack
	Mọi phần tử trong Stack phải cùng kiểu dữ liệu và có thể là bất kỳ kiểu dữ liệu nào, kể cả struct hay object. Một Stack gồm có phần đáy (bottom) và phần đỉnh (top). Phần tử nằm ở đỉnh Stack được gọi là Top Item. Mọi thao tác thêm, xóa phần tử đều diễn ra ở đỉnh Stack. 
b) Nguyên tắc hoạt động của giải thuật đệ quy ứng dụng Stack: 
	- Khi thực hiện một giải thuật đệ quy thì các bước của giải thuật đệ quy sẽ lần lượt được thực hiện tuần tự. 	
 - Khi gặp lời gọi đệ quy thì trước khi thực hiện lời gọi đệ quy, đoạn mã lệnh chưa được thực hiện xong cùng với các đối tượng dữ liệu liên quan tại thời điểm này sẽ được lưu 
vào stack. 
	- Đến lúc nào đó không thể thực hiện lời gọi đệ quy nữa (trường hợp suy biến) thì các đối tượng được lưu trong stack sẽ lần lượt được lấy ra để xử lý.
Ví dụ: Giải thuật đệ quy cho bài toán tính N!
	Giả sử N = 3, quy trình thực hiện như sau:
	- Thực hiện lời gọi hàm: giaithua := gt(3); máy tính sẽ ghi nhớ là: gt(3) := 3 * gt(2); và đi tính gt(2).
	- Tiếp tục máy lại ghi nhớ: gt(2):= 2*gt(1); và đi tính gt(1).
 	- Theo định nghĩa của hàm thì khi gt(1):= 1; máy sẽ quay ngược lại: gt(2):= 2 * 1; và cho kết quả là 2.
	- Tiếp tục: gt(3) := 3 * 2; cho kết quả là 6.
	Như vậy kết quả cuối cùng trả về là 6. Ta có: 3! = 6. 
 	Mặc dù ứng dụng giải toán bằng phương pháp đệ quy kể cả toán học lẫn các ứng dụng trong thực tiễn vẫn còn tồn tại một số ưu – nhược điểm, cụ thể như sau:
c) Ưu điểm và nhược điểm của giải thuật đệ quy:
+ Ưu điểm:
	- Công cụ ứng dụng rất tốt với các bài toán có bản chất đệ quy, thể hiện tư duy rõ ràng và chặt chẽ.
	- Ngắn gọn và có khả năng định nghĩa một tập hợp lớn các đối tượng bằng một số các câu lệnh hữu hạn.
	- Giải thuật đệ quy thực hiện được nhiều bài toán mà giải thuật không đệ quy không thể thực hiện được.
	- Chương trình có chứa giải thuật đệ quy trở nên ngắn gọn, dễ hiểu, nêu bật bản chất vấn đề trong bài toán.
+ Nhược điểm:
	- Chương trình có sử dụng phương pháp đệ quy tốn rất nhiều bộ nhớ hơn khi không dung đệ quy vì cứ mỗi lần gọi đệ quy lại cần thêm một vùng nhớ mới trong khi vùng nhớ cũ vẫn duy trì chưa được giải phóng.
	- Tốc độ thực hiện chương trình chậm hơn khi không dụng đệ quy.
	- Do đệ quy lưu trữ các dữ liệu trung gian vào Stack nên nếu lưu nhiều bộ dữ liệu lớn trên Stack có thể gây ra hiện tượng tràn Stack.
3. Đệ quy quay lui:
a) Khái niệm đệ quy quay lui:
	Quay lui (Backtracking) là phương pháp tìm kiếm lời giải cho các bài toán mà nghiệm của nó là một hay một tập cấu hìn thỏa mãn đồng thời 2 tính chất P và Q, trong đó:
	+ P: Là cách xác định một cấu hình.
	+ Q: Tính dừng của bài toán.
Hay định nghĩa cách khác là: 
	Thuật toán quay lui dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng.
Ví dụ 1:
 Giả sử cấu hình liệt kê có dạng a[1..n], khi đó thuật toán quay lui thực hiện qua các bước
1) Xét tất cả các giá trị a[1] có thể nhận, thử a[1] nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho a[1] ta sẽ:
2) Xét tất cả các giá trị a[2] có thể nhận, thử cho a[2] nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho a[2] lại xét tiếp các khả năng chọn a[3]... cứ tiếp tục như vậy cho đến bước:
.....
n) Xét tất cả các giá trị a[n] có thể nhận, thử cho a[n] nhận lần lượt các giá trị đó, thông báo cấu hình tìm được (a[1], a[2], ..., a[n])
Ví dụ 2:
	Liệt kê tất cả các hoán vị n số tự nhiên nguyên dương đầu tiên theo thứ tự tăng dần của từ điển:
	N = 3: gồm các hoán vị: 123, 132, 213, 231, 312, 321
b) Giải thuật tổng quát của đệ quy quay lui:
Procedure TRY(i: integer);
 Var k: integer;
 Begin
 For k:=1 to n do
 Begin
     Chọn bước đi thứ k
                              If đi được THEN
                                     Begin
                                            Ghi nhận bước đi
                                             If i<n THEN
                                                   Try(i+1)
                                             Else
                                                   In kết quả
                                             Bỏ việc ghi nhận
                                      End;
                  End;
    End;
- Thủ tục bắt đầu hoạt động với Try(1).
- Phân tích giải thuật: 
Nếu một khả năng j nào đó phù hợp cho xi thì xác định xi theo khả năng j. Thường phải thêm thao tác ghi nhận trạng thái mới của bài toán để hỗ trợ cho bước quay lui. Nếu i=n thì ta có được một lời giải, ngược lại thì tiến hành bước i+1 để xác định xi+1
Nếu không có khả năng nào chấp nhận được cho xi thì ta lùi lại bước trước (i-1) để xác định lại thành phần xi-1
Nếu một khả năng j nào đó phù hợp cho xi thì xác định xi theo khả năng j. Thường phải thêm thao tác ghi nhận trạng thái mới của bài toán để hỗ trợ cho bước quay lui. Nếu i=n thì ta có được một lời giải, ngược lại thì tiến hành bước i+1 để xác định xi+1.
Nếu không có khả năng nào chấp nhận được cho xi thì ta lùi lại bước trước (i-1) để xác định lại thành phần xi-1.
- Về bản chất của đệ quy quay lui là quá trình tìm kiếm theo chiều sâu, chúng ta có thể mô tả quá trình tìm kiếm theo sơ đồ cây nhị phân như sau:
Try(2)
Try(2)
Try(1)
Try(3)
Try(3)
Try(3)
Try(3)
Áp dụng: Với bài toán liệt kê tất cả các hoán vị n số tự nhiên nguyên dương đầu tiên theo thứ tự tăng dần của từ điển: Cho N = 3: 
	- Try(k): Tìm thành phần thứ k của hoán vị
	- Duyệt tập các phương án chọn: {1, 2, , N}
	- Chấp nhận được k: Khi k chưa được chọn trước đó.
	- Thực hiện bước chọn: Đánh dấu k đã chọn.
	- Thành công: Khi chọn được thành phần thứ k = N
	- Thông báo kết quả: Hiển thị N số của hoán vị
	- Hủy chọn: Đánh dấu k chưa được chọn.
c) Nét đặc trưng của phương pháp đệ quy quay lui: 
Các bước hướng tới lời giải cuối cùng của bài toán hoàn toàn được làm thử.
Tại một bước:
Nếu có một lựa chọn thì ghi nhận lại lựa chọn và tiến hành các bước thử tiếp theo.
Ngược lại thì làm lại bước trước, xóa bỏ sự ghi nhận và quay về thử các lựa chọn còn lại.
d) Ưu và nhược điểm:
+ Ưu điểm: Việc quay lui là thử tất cả các tổ hợp để tìm được một lời giải. Thế mạnh của phương pháp này là nhiều cài đặt tránh được việc phải thử nhiều trường hợp chưa hoàn chỉnh, nhờ đó giảm thời gian chạy.
+ Nhược điểm: Trong trường hợp xấu nhất độ phức tạp của quay lui vẫn là cấp số mũ. Vì nó mắc phải các nhược điểm sau:
Rơi vào tình trạng "thrashing – thất bại": quá trình tìm kiếm cứ gặp phải bế tắc với cùng một nguyên nhân.
Thực hiện các công việc dư thừa: Mỗi lần chúng ta quay lui, chúng ta cần phải đánh giá lại lời giải trong khi đôi lúc điều đó không cần thiết.
Không sớm phát hiện được các khả năng bị bế tắc trong tương lai. Quay lui chuẩn, không có cơ chế nhìn về tương lai để nhận biết đc nhánh tìm kiếm sẽ đi vào bế tắc.
4. Phương pháp khử đệ quy:
a) Khử đệ quy là gì?
	Khử đệ quy ở đây là biến một thủ tục đệ quy thành một thủ tục chỉ chứa vòng lặp mà không ảnh hưởng gì đến các yếu tố khác, chứ không phải là thay đổi thuật toán.
b) Tại sao phải khử đệ quy ?
	Khử đệ quy là một việc làm phức tạp và khó khăn. Ở hàm n! ta có thể dùng một thuật toán không đệ quy, nhưng trong một số bài toán, đệ quy là bắt buộc. Tuy nhiên đôi khi, sự hạn hẹp của bộ nhớ dành cho chương trình; hoặc ngôn ngữ máy không có đệ quy, vì vậy các trình biên dịch đều phải có nhiệm vụ khử đệ quy.
c) Khử để quy như thế nào ?
	Khử đệ quy thực chất là chúng ta phải làm công việc của một trình biên dịch đối với một thủ tục, đó là: Đặt tất cả các giá trị của các biến cục bộ và địa chỉ của chỉ thị kế tiếp vào Stack, quy định các giá trị tham số cho thủ tục và chuyển tới vị trí bắt đầu thủ tục, thực hiện lần lượt từng câu lệnh. Sau khi thủ tục hoàn tất thì nó phải lấy ra khỏi ng