Bài giảng Kỹ thuật lập trình: Chương 1 - Võ Quang Hoàng Khang

Chương 1 trang bị cho người học kiến thức cơ bản về lập trình đệ quy. Nội dung chính trong chương này gồm có: Khái niệm, thiết kế giải thuật đệ quy, cấu trúc hàm đệ quy, phân loại đệ quy, đệ quy tuyến tính, đệ quy nhị phân, đệ quy hỗ tương,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Kỹ thuật lập trình: Chương 1 - Võ Quang Hoàng KhangVõ Quang Hoàng Khang 1 Cho S(n) = 1 + 2 + 3 + … + n=>S(10)? S(11)? 23 Một hàm được gọi có tính đệ quy nếu trong thân của hàm đó có lệnh gọi lại chính nó. Ví dụ S(n) được tính thông qua S(n-1) 2 điều kiện quan trọng Tồn tại bước đệ quy. Điều kiện dừng. 4 B1. Tham số hoá bài toán. B2. Phân tích trường hợp chung: đưa bài toán về dạng bài toán cùng loại nhưng có phạm vi giải quyết nhỏ hơn theo nghĩa dần tiến đến trường hợp suy biến. B3. Tìm trường hợp suy biến. 5Hàm đệ quy gồm 2 phần: Phần cơ sở: Điều kiện để thoát khỏi đệ quy (điểm dừng) Phần đệ quy: gọi đến chính nó với giá trị mới của tham số nhỏ hơn giá trị ban đầu. Ví dụ: n * (n - 1)! n!  0!  1 6 (n - 1)!* n• Công thức truy hồi tính n!  0!  1• Hàm đệ quy: long GiaiThua( int n ) { if(n==0) return 1; else return GiaiThua(n-1)*n; } 7• Hàm đệ quy nhập mảng 1 chiều: void NhapMang(int a[],int n) { if(n>0) { NhapMang(a,n-1); cin>>a[n-1]; } } 89Trong thân hàm có duy nhất 1 lời gọi hàm gọi lại chính nómột cách tường minh. TenHam () { if (điều kiện dừng) { //Trả về giá trị hay kết thúc công việc } //Thực hiện các công việc (nếu có) . . . TenHam (); //Thực hiện các công việc (nếu có) } 10Ví dụ 1: Tính S (n)  1  2  3    n Điều kiện dừng: S(0) = 0. Công thức truy hồi: S(n) = S(n-1) + n. int TongS (int n) { if(n==0) //điểm dừng return 0; return ( TongS(n-1) + n ); } 11Ví dụ 2: Tính n! long GiaiThua(int n) { if (n==0) //điểm dừng return 1; else return n*GiaiThua(n-1); }với n=5main() GiaiThua(5) GiaiThua(4) GiaiThua(3) GiaiThua(2) GiaiThua(1) 5 4 3 2 1 n 5 n 5 n 4 n 3 n 2 n 1 120 24 6 2 1 12Trong thân hàm có 2 lời gọi hàm gọi lại chính nómột cách tường minh. TenHam () { if (điều kiện dừng) { //Trả về giá trị hay kết thúc công việc } //Thực hiện các công việc (nếu có) . . . TenHam (); //Thực hiện các công việc (nếu có) . . . TenHam (); //Thực hiện các công việc (nếu có) } 13Ví dụ: Tính số hạng thứ n của dãy Fibonaci được định nghĩabởi công thức truy hồi: f0=f1=1 ; fn = fn-1 + fn-2 ; (n>1)Điều kiện dừng: f(0) = f(1) = 1.long Fibonaci(int n){ if(n==0 || n==1) return 1; return Fibonaci(n-1)+ Fibonaci(n-2);} 14Trong thân của hàm có lời gọi hàm gọi lại chính nó được đặt bên trong vònglặp. TenHam () { for (int i = 1; iVí dụ: Tính số hạng thứ n của dãy {Xn} được định nghĩa như sau: X0 =1 ; Xn = n2X0 + (n-1)2X1 + … + 12Xn-1 ; (n≥1)Điều kiện dừng: X(0) = 1.long TinhXn(int n){ if(n==0) return 1; long s = 0; for (int i=1; iTrong thân của hàm này có lời gọi hàm đến hàm kia vàngược lại. g() f() f() f() g() h() 17 TenHam2 (); TenHam1 (){ //Thực hiện một số công việc (nếu có) …TenHam2 (); //Thực hiện một số công việc (nếu có)} TenHam2 (){ //Thực hiện một số công việc (nếu có) …TenHam1 (); //Thực hiện một số công việc (nếu có)} 18Ví dụ: Tính số hạng thứ n của hai dãy {Xn}, {Yn} được định nghĩa như sau:X0 =Y0 =1 ;Xn = Xn-1 + Yn-1; (n>0)Yn = n2Xn-1 + Yn-1; (n>0)- Điều kiện dừng: X(0) = Y(0) = 1.long TinhYn(int n);long TinhXn (int n){ if(n==0) return 1; return TinhXn(n-1) + TinhYn(n-1);}//----------------------------------------------------------------------long TinhYn (int n){ if(n==0) return 1; 19 return ...