Bài giảng Kỹ thuật lập trình đệ quy - Chương 6: Lập trình Hàm (Phần 2)

02/2012 
Chương 6: Lập trình Hàm (Phần 2) 
02/2012 
Nội dung 
Kỹ thuật lập trình đệ quy 
Tổng quan về đệ quy 
1 
Các vấn đề đệ quy thông dụng 
2 
Phân tích giải thuật & khử đệ quy 
4 
Các bài toán kinh đ iển 
3 
02/2012 
Bài toán 
Cho S(n) = 1 + 2 + 3 +  + n 
	=>S( 10 )? S( 11 )? 
Kỹ thuật lập trình đệ quy 
1 
+ 
2 
+ 
+ 
10 
1 
+ 
2 
+ 
+ 
10 
= 
55 
+ 
11 
= 
66 
1 
+ 
2 
+ 
+ 
10 
= 
= 
S( 10 ) 
S( 11 ) 
1 
+ 
2 
+ 
+ 
10 
S(10) 
= 
+ 
11 
= 
+ 
11 
55 
= 
66 
S( 10 ) 
+ 
11 
55 
+ 
11 
02/2012 
2 b ướ c giải bài toán 
Kỹ thuật lập trình đệ quy 
= 
S(n) 
+ 
n 
S(n-1) 
= 
S(n-1) 
+ 
n-1 
S(n-2) 
= 
+ 
= 
S(1) 
+ 
1 
S(0) 
= 
S(0) 
0 
B ướ c 1. Phân tích 
Phân tích thành bài toán đồ ng dạng nh ư ng đơ n giản h ơ n. 
Dừng lại ở bài toán đồ ng dạng đơ n giản nhất có thể xác đị nh ngay kết quả. 
B ướ c 2. Thế ng ượ c 
Xác đị nh kết quả bài toán đồ ng dạng từ đơ n giản đế n phức tạp Kết quả cuối cùng. 
02/2012 
Khái niệm đệ quy 
Kỹ thuật lập trình đệ quy 
Khái niệm 
Vấn đề đệ quy là vấn đề đượ c đị nh nghĩa bằng chính nó. 
Ví dụ 
Tổng S(n) đượ c tính thông qua tổng S(n-1) . 
2 đ iều kiện quan trọng 
 Tồn tại b ướ c đệ quy. 
 Điều kiện dừng. 
02/2012 
Hàm đệ quy trong NNLT C 
Khái niệm 
Một hàm đượ c gọi là đệ quy nếu bên trong thân của hàm đó có lời gọi hàm lại chính nó một cách trực tiếp hay gián tiếp. 
Kỹ thuật lập trình đệ quy 
 Hàm() 
{ 
 Lời gọi Hàm 
} 
ĐQ trực tiếp 
 Hàm1() 
{ 
 Lời gọi Hàm2 
} 
ĐQ gián tiếp 
 Hàm2() 
{ 
 Lời gọi Hàm1 
} 
02/2012 
Cấu trúc hàm đệ quy 
Kỹ thuật lập trình đệ quy 
{ 
 if () 
 { 
 return ; 
 } 
  Lời gọi Hàm 
} 
 (TS) 
Phần dừng 
(Base step) 
Phần khởi tính toán hoặc điểm kết thúc của thuật toán 
Không chứa phần đang được định nghĩa 
Phần đệ quy 
(Recursion step) 
Có sử dụng thuật toán đang được định nghĩa. 
02/2012 
Phân loại 
Kỹ thuật lập trình đệ quy 
2 
TUYẾN TÍNH 
NHỊ PHÂN 
HỖ T ƯƠ NG 
PHI TUYẾN 
1 
3 
4 
Trong thân hàm có duy nhất một lời gọi hàm gọi lại chính nó một cách t ườ ng minh . 
Trong thân hàm có hai lời gọi hàm gọi lại chính nó một cách t ườ ng minh . 
Trong thân hàm này có lời gọi hàm tới hàm kia và bên trong thân hàm kia có lời gọi hàm tới hàm này . 
Trong thân hàm có lời gọi hàm lại chính nó đượ c đặ t bên trong thân vòng lặp . 
02/2012 
 TênHàm () { 
 if () { 
 return ; 
 } 
  TênHàm ();  
} 
Cấu trúc ch ươ ng trình 
Đệ quy tuyến tính 
Kỹ thuật lập trình đệ quy 
Tính S(n) = 1 + 2 +  + n 
 S(n) = S(n – 1) + n 
ĐK dừng: S(0) = 0 
.: Ch ươ ng trình :. 
long Tong (int n) 
{ 
 if (n == 0) 
 return 0; 
 return Tong (n–1) + n; 
} 
Ví dụ 
02/2012 
 TênHàm () { 
 if () { 
 return ; 
 } 
  TênHàm (); 
  TênHàm (); 
} 
Cấu trúc ch ươ ng trình 
Đệ quy nhị phân 
Kỹ thuật lập trình đệ quy 
Tính số hạng thứ n của dãy Fibonacy : 
f(0) = f(1) = 1 
f(n) = f(n – 1) + f(n – 2) n > 1 
ĐK dừng : f(0) = 1 và f(1) = 1 
.: Ch ươ ng trình :. 
long Fibo (int n) 
{ 
 if (n == 0 || n == 1) 
 return 1; 
 return Fibo (n–1)+ Fibo (n–2); 
} 
Ví dụ 
02/2012 
 TênHàm1 () { 
 if () 
 return ; 
  TênHàm2 ();  
} 
 TênHàm2 () { 
 if () 
 return ; 
  TênHàm1 ();  
} 
Cấu trúc ch ươ ng trình 
Đệ quy hỗ t ươ ng 
Kỹ thuật lập trình đệ quy 
Tính số hạng thứ n của dãy : 
x(0) = 1, y(0) = 0 
x(n) = x(n – 1) + y(n – 1) 
y(n) = 3*x(n – 1) + 2*y(n – 1) 
ĐK dừng : x(0) = 1, y(0) = 0 
.: Ch ươ ng trình :. 
long y (int n); 
long x (int n) { 
 if (n == 0) return 1; 
 return x (n-1)+ y (n-1); 
} 
long y (int n) { 
 if (n == 0) return 0; 
 return 3* x (n-1)+2* y (n-1); 
} 
Ví dụ 
02/2012 
 TênHàm () { 
 if () { 
 return ; 
 } 
  Vòng lặp { 
  TênHàm ();  
 } 
} 
Cấu trúc ch ươ ng trình 
Đệ quy phi tuyến 
Kỹ thuật lập trình đệ quy 
Tính số hạng thứ n của dãy : 
x(0) = 1 
x(n) = n 2 x(0) + (n-1) 2 x(1) +  + 2 2 x(n – 2) + 1 2 x(n – 1) 
ĐK dừng : x(0) = 1 
.: Ch ươ ng trình :. 
long x (int n) 
{ 
 if (n == 0) return 1; 
 long s = 0; 
 for (int i=1; i<=n; i++) 
 s = s + i*i* x (n–i); 
 return s; 
} 
Ví dụ 
02/2012 
Các b ướ c xây dựng hàm đệ quy 
Kỹ thuật lập trình đệ quy 
 Tìm các tr ườ ng hợp suy biến (neo) 
Tổng quát hóa bài toán cụ thể thành bài toán tổng quát. 
VD: n trong hàm tính tổng S( n ),  
Chia bài toán tổng quát ra thành: 
Phần không đệ quy. 
Phần nh ư bài toán trên nh ư ng kích th ướ c nhỏ h ơ n. 
VD: S(n) = S(n – 1) + n,  
Các tr ườ ng hợp suy biến của bài toán. 
Kích th ướ c bài toán trong tr ườ ng hợp này là nhỏ nhất. 
VD: S(0) = 0 
Tìm thuật giải 
tổng quát 
 Tổng quát hóa 
bài toán 
02/2012 
C ơ chế gọi hàm và STACK 
Kỹ thuật lập trình đệ quy 
{ 
 ; 
 A(); 
 ; 
 D(); 
 ; 
} 
main() 
{ 
 ; 
 B(); 
 ; 
 C(); 
 ; 
} 
A() 
{ 
 ; 
} 
C() 
{ 
 ; 
 D(); 
 ; 
} 
B() 
{ 
 ; 
} 
D() 
main 
A 
B 
C 
D 
D 
M 
M 
A 
M 
A 
B 
M 
A 
M 
A 
B 
M 
A 
M 
A 
C 
M 
M 
M 
D 
B 
D 
A 
M 
STACK 
Thời gian 
02/2012 
Nhận xét 
C ơ chế gọi hàm dùng STACK trong C phù hợp cho giải thuật đệ quy vì : 
Lưu thông tin chương trình còn dở dang mỗi khi gọi đệ quy. 
Thực hiện xong một lần gọi cần khôi phục thông tin chương trình trước khi gọi. 
Lệnh gọi cuối cùng sẽ hoàn tất đầu tiên. 
Kỹ thuật lập trình đệ quy 
02/2012 
Ví dụ gọi hàm đệ quy 
Tính số hạng thứ 4 của dãy Fibonacy 
Kỹ thuật lập trình đệ quy 
F(4) 
F(2) 
F(3) 
F(1) 
F(2) 
F(1) 
F(0) 
+ 
+ 
+ 
1 
1 
2 
2 
1 
3 
3 
F(1) 
F(0) 
+ 
1 
1 
2 
2 
5 
5 
02/2012 
Một số lỗi th ườ ng gặp 
Công thức đệ quy chưa đúng, không tìm đượ c bài toán đồ ng dạng đơ n giản h ơ n ( không hội tụ) nên không giải quyết được vấn đề. 
Không xác đị nh các tr ườ ng hợp suy biến – neo ( đ iều kiện dừng). 
Thông điệp thường gặp là StackOverflow do: 
Thuật giải đệ quy đú ng nh ư ng số lần gọi đệ quy quá lớn làm tràn STACK. 
Thuật giải đệ quy sai do không hội tụ hoặc không có đ iều kiện dừng. 
Kỹ thuật lập trình đệ quy 
02/2012 
Nội dung 
Kỹ thuật lập trình đệ quy 
Tổng quan về đệ quy 
1 
Các vấn đề đệ quy thông dụng 
2 
Phân tích giải thuật & khử đệ quy 
4 
Các bài toán kinh đ iển 
3 
02/2012 
Các vấn đề đệ quy thông dụng 
Kỹ thuật lập trình đệ quy 
Đệ quy?? 
02/2012 
1.Hệ thức truy hồi 
Khái niệm 
Hệ thức truy hồi của 1 dãy A n là công thức biểu diễn phần tử A n thông qua 1 hoặc nhiều số hạng trước của dãy. 
Kỹ thuật lập trình đệ quy 
A 0 
A 1 
A n-1 
A n-2 
A n-1 
A n 
Hàm truy hồi 
A 0 
A 1 
A n-1 
A n-2 
A n-1 
A n 
A n-2 
Hàm truy hồi 
02/2012 
1.Hệ thức truy hồi 
Ví dụ 1 
Vi trùng cứ 1 giờ lại nhân đô i. Vậy sau 5 giờ sẽ có mấy con vi trùng nếu ban đầ u có 2 con? 
Giải pháp 
Gọi V h là số vi trùng tại thời đ iểm h. 
Ta có: 
V h = 2V h-1 
V 0 = 2 
	 Đ ệ quy tuyến tính với V(h)=2*V(h-1) và đ iều kiện dừng V(0) = 2 
Kỹ thuật lập trình đệ quy 
02/2012 
1.Hệ thức truy hồi 
Ví dụ 2 
Gửi ngân hàng 1000 USD, lãi suất 12%/n ă m. Số tiền có đượ c sau 30 n ă m là bao nhiêu? 
Giải pháp 
Gọi T n là số tiền có đượ c sau n n ă m. 
Ta có: 
T n = T n-1 + 0.12T n-1 = 1.12T n-1 
T(0) = 1000 
	 Đ ệ quy tuyến tính với T(n)=1.12*T(n-1) và đ iều kiện dừng T(0) = 1000 
Kỹ thuật lập trình đệ quy 
02/2012 
2.Chia để trị (divide & conquer) 
Khái niệm 
Chia bài toán thành nhiều bài toán con. 
Giải quyết từng bài toán con. 
Tổng hợp kết quả từng bài toán con để ra lời giải. 
Kỹ thuật lập trình đệ quy 
02/2012 
2.Chia để trị (divide & conquer) 
Ví dụ 1 
Cho dãy A đã sắp xếp thứ tự t ă ng. Tìm vị trí phần tử x trong dãy (nếu có) 
Giải pháp 
mid = (l + r) / 2; 
Nếu A[mid] = x trả về mid. 
Ng ượ c lại 
Nếu x < A[mid] tìm trong đ oạn [l, mid – 1] 
Ng ượ c lại tìm trong đ oạn [mid + 1, r] 
	 Sử dụng đ ệ quy nhị phân. 
Kỹ thuật lập trình đệ quy 
02/2012 
2.Chia để trị (divide & conquer) 
Ví dụ 2 
Tính tích 2 chuỗi số cực lớn X và Y 
Giải pháp 
X = X 2n-1 X n X n-1 X 0 , Y = Y 2n-1 Y n Y n-1 Y 0 
Đặt X L =X 2n-1 X n , X N =X n-1 X 0 X=10 n X L +X N 
Đặt Y L =Y 2n-1 Y n , Y N =Y n-1 Y 0 Y=10 n Y L +Y N 
	 X*Y = 10 2n X L Y L + 10 n (X L Y L +X N Y N )+X N Y N 
	 Nhân 2 số nhỏ h ơ n ( độ dài ½) đế n khi có thể nhân đượ c ngay. 
Kỹ thuật lập trình đệ quy 
02/2012 
2.Chia để trị (divide & conquer) 
Một số bài toán khác 
Bài toán tháp Hà Nội 
Các giải thuật sắp xếp: QuickSort, MergeSort 
Các giải thuật tìm kiếm trên cây nhị phân tìm kiếm, cây nhị phân nhiều nhánh tìm kiếm. 
L ư u ý 
Khi bài toán lớn được chia thành các bài toán nhỏ hơn mà những bài toán nhỏ hơn này không đơn giản nhiều so với bài toán gốc thì không nên dùng kỹ thuật chia để trị . 
Kỹ thuật lập trình đệ quy 
02/2012 
3.Lần ng ượ c (Backtracking) 
Khái niệm 
Tại b ướ c có nhiều lựa chọn, ta chọn thử 1 b ướ c để đ i tiếp. 
Nếu không thành công thì “lần ng ượ c” chọn b ướ c khác. 
Nếu đã thành công thì ghi nhận lời giải này đồ ng thời “lần ng ượ c” để truy tìm lời giải mới. 
Thích hợp giải các bài toán kinh đ iển nh ư bài toán 8 hậu và bài toán mã đ i tuần. 
Kỹ thuật lập trình đệ quy 
02/2012 
3.Lần ng ượ c (Backtracking) 
Ví dụ 
Tìm đườ ng đ i từ X đế n Y . 
Kỹ thuật lập trình đệ quy 
X 
D 
A 
C 
Y 
B 
02/2012 
Nội dung 
Kỹ thuật lập trình đệ quy 
Tổng quan về đệ quy 
1 
Các vấn đề đệ quy thông dụng 
2 
Phân tích giải thuật & khử đệ quy 
4 
Các bài toán kinh đ iển 
3 
02/2012 
1 
2 
3 
1 
3 
2 
# 
$ 
@ 
Một số bài toán kinh đ iển 
Kỹ thuật lập trình đệ quy 
TÁM HẬU 
THÁP HÀ NỘI 
PHÁT SINH HOÁN VỊ 
MÃ ĐI TUẦN 
02/2012 
Tháp Hà Nội 
Mô tả bài toán 
Có 3 cột A, B và C và cột A hiện có N đĩ a. 
Tìm cách chuyển N đĩ a từ cột A sang cột C sao cho: 
Một lần chuyển 1 đĩ a 
Đ ĩa lớn h ơ n phải nằm d ướ i. 
Có thể sử dụng các cột A, B, C làm cột trung gian. 
Kỹ thuật lập trình đệ quy 
02/2012 
Tháp Hà Nội 
Kỹ thuật lập trình đệ quy 
Cột nguồn A 
Cột trung gian B 
Cột đí ch C 
1 
N-1 
1 
N-1 
N 
N-1 đĩa A B 
N đĩa A C 
N-1 đĩa B C 
Đĩa N A C 
= 
+ 
+ 
? 
02/2012 
Tám hậu 
Mô tả bài toán 
Cho bàn cờ vua kích th ướ c 8x8 
Hãy đặ t 8 hoàng hậu lên bàn cờ này sao cho không có hoàng hậu nào “ ă n” nhau: 
Không nằm trên cùng dòng, cùng cột 
Không nằm trên cùng đườ ng chéo xuôi, ng ượ c. 
Kỹ thuật lập trình đệ quy 
02/2012 
Tám hậu – Các dòng 
Kỹ thuật lập trình đệ quy 
0 
1 
2 
3 
4 
5 
6 
7 
n đườ ng 
02/2012 
Tám hậu – Các cột 
Kỹ thuật lập trình đệ quy 
0 
1 
2 
3 
4 
5 
6 
7 
n đườ ng 
02/2012 
Tám hậu – Các đườn g chéo xuôi 
Kỹ thuật lập trình đệ quy 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
2n-1 đườ ng 
02/2012 
Tám hậu – Các đườn g chéo ng ượ c 
Kỹ thuật lập trình đệ quy 
0 
1 
2 
3 
4 
5 
6 
7 
14 
13 
12 
11 
10 
9 
8 
2n-1 đườ ng 
02/2012 
Tám hậu – Các dòng 
Kỹ thuật lập trình đệ quy 
j = 3 
i = 2 
j-i+n-1=8 
j+i=5 
02/2012 
Mã đ i tuần 
Mô tả bài toán 
Cho bàn cờ vua kích th ướ c 8x8 (64 ô) 
Hãy đ i con mã 64 n ướ c sao cho mỗi ô chỉ đ i qua 1 lần (xuất phát từ ô bất kỳ) theo luật: 
Kỹ thuật lập trình đệ quy 
4 
7 
3 
8 
5 
6 
2 
1 
02/2012 
Nội dung 
Kỹ thuật lập trình đệ quy 
Tổng quan về đệ quy 
1 
Các vấn đề đệ quy thông dụng 
2 
Phân tích giải thuật & khử đệ quy 
4 
Các bài toán kinh đ iển 
3 
02/2012 
Phân tích giải thuật đệ quy 
Sử dụng cây đệ quy  (recursive tree) 
Giúp hình dung b ướ c phân tích và thế ng ượ c. 
B ướ c phân tích : đ i từ trên xuống d ướ i. 
B ướ c thế ng ượ c đ i từ trái sang phải , từ d ướ i lên trên . 
Ý nghĩa 
Chiều cao của cây  Độ lớn trong STACK. 
Số nút  Số lời gọi hàm . 
Kỹ thuật lập trình đệ quy 
02/2012 
Nhận xét 
Ư u đ iểm 
Sáng sủa, dễ hiểu, nêu rõ bản chất vấn đề . 
Tiết kiệm thời gian thực hiện mã nguồn. 
Một số bài toán rất khó giải nếu không dùng đệ qui. 
Khuyết đ iểm 
Tốn nhiều bộ nhớ, thời gian thực thi lâu. 
Một số tính toán có thể bị lặp lại nhiều lần. 
Một số bài toán không có lời giải đệ quy. 
Kỹ thuật lập trình đệ quy 
02/2012 
Ví dụ cây đệ quy Fibonacy 
Kỹ thuật lập trình đệ quy 
F(4) 
F(2) 
F(3) 
F(1) 
F(2) 
F(1) 
F(0) 
F(1) 
F(0) 
Lặp lại 
02/2012 
Khử đệ quy (tham khảo) 
Khái niệm 
Đ ư a các bài toán đệ quy về các bài toán không sử dụng đệ quy. 
Th ườ ng sử dụng vòng lặp hoặc STACK tự tạo. 
Kỹ thuật lập trình đệ quy 
02/2012 
Tổng kết 
Nhận xét 
Chỉ nên dùng ph ươ ng pháp đệ quy để giải các bài toán kinh đ iển nh ư giải các vấn đề “chia để trị”, “lần ng ượ c”. 
Vấn đề đệ quy không nhất thiết phải giải bằng ph ươ ng pháp đệ quy, có thể sử dụng ph ươ ng pháp khác thay thế ( khử đệ quy ) 
Tiện cho ng ườ i lập trình nh ư ng không tối ư u khi chạy trên máy. 
B ướ c đầ u nên giải bằng đệ quy nh ư ng từng b ướ c khử đệ quy để nâng cao hiệu quả. 
Kỹ thuật lập trình đệ quy 
02/2012 
Bài tập 
Bài 1: 
Kỹ thuật lập trình đệ quy 
a. 
b. 
c. 
d. 
e. 
f. 
02/2012 
Bài tập 
Bài 2: Tính n! 
Bài 3: Tính x n 
Bài 4: Tính S(n) = 1+1.2+1.2.3++1.2.3n 
Bài 5: Hãy đếm số lượng chữ số của số n guyên dương n. 
Bài 6: Tính phần tử thứ n của dãy Fibonacci. 
F(0) = 1, F(1) = 1; 
F(n) = F(n-1) + F(n-2) 
Bài 7: Viết hàm đệ quy tính C(n, k) biết 
C(n, k) = 1 nếu k = 0 hoặc k = n 
C(n, k) = 0 nếu k > n 
C(n ,k) = C(n-1, k) + C(n-1, k-1) nếu 0<k<n 
Kỹ thuật lập trình đệ quy 
02/2012 
Bài tập 
Bài 8: Cho dãy an như sau:a0 =1; a1=0; a2 =-1;an = 2an-1 – 3an-2 - an-3 (n>2)Viết chương trình tính số hạng thứ n của dãy bằng hai cách:a) Sử dụng kỹ thuật đệ qui.b) Không sử dụng kỹ thuật đệ qui. 
Kỹ thuật lập trình đệ quy 
02/2012 
Hết