Bài giảng Lập trình C++ - Chương 3: Lập trình đệ qui

Chương 3: LẬP TRÌNH ĐỆ QUI 1. Tổng quan về lập trình đệ qui 2. Đệ qui tuyến tính 3. Đệ qui nhị phân 4. Đệ qui phi tuyến 5. Đệ qui tương hỗ 1.Tổng quan về lập trình đệ qui • Đệ qui là hàm cho phép gọi đến chính hàm đó • Trong lập trình đệ qui sẽ bao gồm 2 phần: – Phần neo:Là phần cơ sở, cho phép tính một giá trị cụ thể – Phần đệ qui:Cho phép gọi lại chính hàm đó để tính giá trị hiện tại của hàm bằng cách gọi các hàm tính giá trị ở bước trước đó. • Có 4 loại đệ qui là đệ qui tuyến tính, đệ qui nhị phân, đệ qui phi tuyến và đệ qui tương hỗ. 2. Đệ qui tuyến tính • Là loại hàm đệ qui phổ biến nhất. • Nó có cú pháp như sau: Ham { if() { Trả về kết quả hoặc kết thúc công việc } else { Thực hiên công việc – nếu cần Gọi đệ qui } } 2. Đệ qui tuyến tính • Ví dụ: Viết hàm đệ qui tính n! – Định nghĩa: n! = 1x2x.x(n-1)xn. Ta có: • 1!=1; • 2! = 1 x 2  2 X 1! • 3! = 1 x 2 x 3  3 X 2! • 4! = 1 x 2 x 3 x 4  4 x 3! • • n!=1 x 2 x 3 x.x (n-1) x n  (n-1)! x n 3. Đệ qui nhị phân • Là loại hàm đệ qui cho phép chia ra thành những việc nhỏ hơn, không cồng kềnh. • Cú pháp Ham { if() { Trả về kết quả hoặc kết thúc công việc } else { Thực hiên công việc – nếu cần Gọi đệ qui 1()//Giải quyết việc nhỏ hơn Gọi đệ qui 2()//Giải quyết phần còn lại } } 3. Đệ qui nhị phân • Ví dụ: – Tìm số fibo thứ n có thể tính bằng cách: • Tìm F(n-1) • Tìm F(n-2) • ret=F(n -1)+F(n-2); – Tìm phần tử lớn nhất, bé nhất ở trong mảng. • Tìm giá trị lớn nhất ở bên trái • Tìm giá trị lớn nhất ở bên phải • So sánh giá trị lớn nhất, nhỏ nhất ở bên trái, bên phải tìm giá trị lớn nhất, nhỏ nhất. 4. Đệ qui phi tuyến • Đệ qui phi tuyến cho phép gọi đệ qui bên trong vòng lặp. • Cú pháp Ham { for(i=0;i<n;i++) { //Thực hiện một số công việc nếu cần if(điều kiện dừng) { //Làm một số công việc nếu cần } else } } 4. Đệ qui phi tuyến • Ví dụ: Tìm dãy {Xn} xác định theo công thức truy hồi sau đây: Xo = 1 Xn = n 2Xo +(n-1) 2X1++1 2Xn-1 nếu n>=1 Nếu n = 0 => Xo =1 n = 1 => X1 = 1 n = 2 => 22x1 +12x1 = 5 n = 3 => 32x1 + 22 x 1 + 1x5 = 18 n = 4 => 42x1+32x1+22x5+12x18 = 63 5. Đệ qui tương hỗ • Là loại hàm đệ qui gọi lại chính nó thông qua 1 hàm khác. • Cú pháp: Ham1 { //Làm 1 số việc nếu cần Ham2(..); //Làm 1 số việc nếu cần } Ham2 { //Làm 1 số việc nếu cần Ham1(..); //Làm 1 số việc nếu cần } 5. Đệ qui tương hỗ • Ví dụ: Hai dãy {Xn}, {Yn} được định nghĩa Xo=Yo = 1 Xn=Xn-1 + Yn-1 Yn=n 2Xn-1 + Yn-1 Nếu n =0 => Xo = Yo = 1 n = 1 => X1 = 1+1 = 2 Y1 = 1 2x1 + 1 = 2 n =2 => X2 = 2 + 2 = 4 Y2= 2 2x2 + 2 = 10