TRƢỜNG CAO ĐẲNG CNTT TP.HCM KHOA CÔNG NGHỆ THÔNG TIN

KỸ THUẬT LẬP TRÌNH NÂNG CAO

Chƣơng 3 LẬP TRÌNH ĐỆ QUI

Giảng Viên: ThS. Dƣơng Thành Phết Email: phetcm@gmail.com Website: http://www.thayphet.net Tel: 0918158670 – facebook.com/DuongThanhPhet

1. KHÁI NIỆM

 Một hàm được gọi có tính đệ qui nếu trong thân của hàm đó có lệnh gọi lại chính nó một cách tường minh hay tiềm ẩn.

 Phân loại đệ qui

 Đệ qui tuyến tính.

 Đệ qui nhị phân.

 Đệ qui phi tuyến.

 Đệ qui hỗ tương.

2

2. ĐỆ QUI TUYẾN TÍNH

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.

//Trả về giá trị hay kết thúc công việc

if (điều kiện dừng) //Thực hiện một số công việc (nếu có) …TenHam (); //Thực hiện một số công việc (nếu có)

3

TenHam () { }

2. ĐỆ QUI TUYẾN TÍNH

Ví dụ: Tính

- Điều kiện dừng: S(0) = 0.

- Qui tắc (công thức) tính: S(n) = S(n-1) + n.

return 0;

long TongS (int n) { return ( TongS(n-1) + n ); }

4

if(n==0)

3. ĐỆ QUI NHỊ PHÂN

Trong thân của hàm có hai lời gọi hàm gọi lại chính nó một cách tường minh.

if (điều kiện dừng) //Thực hiện một số công việc (nếu có) ….TenHam (); //Thực hiện một số công việc (nếu có) . . . TenHam (); //Giải quyết vấn đề còn lại //Thực hiện một số công việc (nếu có)

5

//Trả về giá trị hay kết thúc công việc

TenHam () { }

3. ĐỆ QUI NHỊ PHÂN

Ví dụ: Tính số hạng thứ n của dãy Fibonaci được định nghĩa như sau:

Điều kiện dừng: f(0) = f(1) = 1.

if(n==0 || n==1)

(n>1) f1 = f0 =1 ; fn = fn-1 + fn-2 ;

return 1;

Fibonaci(n-2);

long Fibonaci (int n) { return Fibonaci(n-1) +

6

}

4. ĐỆ QUI PHI TUYẾN

//Trả về giá trị hay kết thúc công việc

Trong 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òng lặp.

//Thực hiện một số công việc (nếu có) TenHam ();

//Thực hiện một số công việc (nếu có) if (điều kiện dừng) else { }

for (int i = 1; i<=n; i++) { }

TenHam () { }

7

4. ĐỆ QUI PHI TUYẾN

(n≥1) X0 =1 ; Xn = n2X0 + (n-1)2X1 + … + 12Xn-1 ;

Ví dụ: Tính số hạng thứ n của dãy {Xn} được định nghĩa như sau: Điều kiện dừng:X(0) = 1.

if(n==0) long s = 0; for (int i=1; i<=n; i++)

return 1;

8

s = s + i * i * TinhXn(n-i);

long TinhXn (int n) { return s; }

5. ĐỆ QUI TƢƠNG HỖ

9

Trong thân của hàm này có lời gọi hàm đến hàm kia và trong thân của hàm kia có lời gọi hàm tới hàm này.

5. ĐỆ QUI TƢƠNG HỖ

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ó)

}

10

5. ĐỆ QUI TƢƠNG HỖ

Ví dụ: Tính số hạng thứ n của hai dãy {Xn}, {Yn} được định nghĩa như sau:

(n>0)

(n>0)

11

X0 =Y0 =1 ; Xn = Xn-1 + Yn-1; Yn = n2Xn-1 + Yn-1; Điều kiện dừng:X(0) = Y(0) = 1.

5. ĐỆ QUI TƢƠNG HỖ

if(n==0) return 1;

if(n==0) return 1;

12

long TinhYn(int n); long TinhXn (int n) { return TinhXn(n-1) + TinhYn(n-1); } long TinhYn (int n) { return n*n*TinhXn(n-1) + TinhYn(n-1); }

6. CÁCH HOẠT ĐỘNG HÀM ĐỆ QUI

13

Ví dụ: tính n! với n=5

The End.

14