Bài giảng Phương pháp lập trình - Chương VIII: Đệ quy - Nguyễn Văn Thắng

Nội dung text: Bài giảng Phương pháp lập trình - Chương VIII: Đệ quy - Nguyễn Văn Thắng

1. CHƯƠNG VIII:ĐỆ QUY
2. Định nghĩa • Một hàm được gọi là đệ quy nếu bên trong thân hàm có lệnh gọi đến chính nó. • Ví dụ: n!=1* 2 * 3 * * (n-1) *n = (n-1)! *n (với 0!=1) Như vậy, để tính n! : nếu n=0 thì n!=1 ngược lại thì n!=n * (n-1)!
3. Ví dụ: Hàm tính giai thừa đệ quy int giaithua(int n) { if(n==0) return 1; else return n*giaithua(n-1); }
4. Phân loại đệ quy
5. Đệ quy tuyến tính • Cú pháp: KDL TenHam( ) { if( ) { return ; } TenHam( ); }
6. Ví dụ: Tính S(n)=1+2+3+ +n long int TongSn(int n) { if(n==0) return 0; return (TongSn(n-1)+n); }
7. Đệ quy nhị phân • Cú pháp: KDL TenHam( ) { if( ) { return ; } TenHam( ); TenHam( ); }
8. Ví dụ: Tính số hạng thứ n của dãy Fibonaci Nếu f(0)=f(1)=1 f(n)=f(n-1)+f(n-2), n>1 long int Fibonaci(int n) { if(n= =0 || n= =1) return 1; return (Fibonaci(n-1)+Fibonaci(n-2)); }
9. Đệ quy phi tuyến • Chương trình con đệ quy phi tuyến là chương trình con đệ quy trực tiếp mà lời gọi đệ quy được thực hiện bên trong vòng lặp .
10. Cú pháp: KDL TenHam( ) { for(int i=1; i ) { } else { TenHam( ); } } }
11. Ví dụ:Tìm số hạng thứ n của dãy: n2x(0)+(n-1)2x(1)+(n-2)2x(2)+ +22x(n-2)+12x(n-1) x(0)=0 x(n)=n2x(0)+(n-1)2x(1)+(n-2)2x(2)+ +22x(n-2)+12x(n-1) long int TinhXn(int n) { if(n==0) return 1; long int s=0; for(int i=1; i<=n; i++) s+=i*i*TinhXn(n-i); return s; }
12. Đệ quy hỗ tương KDL TenHam2( ); KDL TenHam1( ) { TenHam2( ); } KDL TenHam2( ) { TenHam1( ); }
13. Ví dụ: Tìm số hạng thứ n của dãy sau: x(0)=1 y(0)=0 x(n)=x(n-1)+y(n-1) khi n>0 y(n)=3*x(n-1)-2*y(n-1) khi n>0 long int TinhYn(int n); long int TinhXn(int n) { if(n==0) return 1; return TinhXn(n-1)+TinhYn(n-1); } long int TinhYn(int n) { if(n==0) return 0; return 3*TinhXn(n-1)-2*TinhYn(n-1); }
14. Đặc điểm cần lưu ý khi viết hàm đệ quy Hàm đệ quy phải có 2 phần: • Phần dừng hoặc phải có trường hợp nguyên tố. Trong các ví dụ trên thì trường hợp n=0 là trường hợp nguyên tố. • Phần đệ quy: là phần có gọi lại hàm đang được định nghĩa. Trong ví dụ trên thì phần đệ quy là n>0 thì n! = n * (n-1)!
15. Ví dụ:tính S(n) = 2 + 2 + 2 + + 2 float tongcan(int n) { if(n==1) return sqrt(2); return sqrt(2+tongcan(n-1)) }