Bài giảng Kỹ thuật lập trình nâng cao: Chương 7 - Trần Minh Thái

Chia sẻ: Y Nhân | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

37
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Kỹ thuật lập trình nâng cao - Chương 7: Lập trình đệ quy" cung cấp cho người học các kiến thức: Đệ quy tuyến tính, đệ quy nhị phân, đệ quy phi tuyến, đệ quy hỗ tương, các hoạt động hàm đệ quy. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Kỹ thuật lập trình nâng cao: Chương 7 - Trần Minh Thái

* Trần Minh Thái minhthai@itc.edu.vn 1
* *Một hàm được gọi có tính đệ qui nếu trong thân của hàm đó có lệnh gọi lại chính nó một cách tường minh hay tiềm ẩn. *Phân loại đệqui *Đệ qui tuyến tính. *Đệqui nhịphân. *Đệqui phi tuyến. *Đệqui hỗtương. 2
* • Trong thân hàm có duy nhất một lời gọi hàm gọi lại chính nómột cách tường minh. TenHam () { if (điều kiện dừng) { ... //Trảvềgiátrịhay kết thúc công việc } //Thực hiện một sốcông việc (nếu có) . . . TenHam (); //Thực hiện một sốcông việc (nếu có) } 3
Vídụ: Tính S ( n ) = 1 + 2 + 3 + L + n - Điều kiện dừng: S(0) = 0. - Qui tắc (công thức) tính: S(n) = S(n-1) + n. int TongS (int n) { if(n==0) return 0; return ( TongS(n-1) + n ); } 4
* 1. Tính n! 2. In ra các ước số của số nguyên dương 3. Đếm số lượng ước số của số nguyên dương 4. Tìm ước số chung lớn nhất của 2 số nguyên dương 5. Kiểm tra số nguyên dương n có phải là số nguyên tố? 6. Nhập vào mảng 1 chiều số nguyên a, kích thước n 7. Xuất mảng 1 chiều số nguyên a, kích thước n 8. Tìm phần tử có giá trị x trong mảng số nguyên a, kích thước n 5
* Trong thân của hàm cóhai lời gọi hàm gọi lại chính nómột cách tường minh. TenHam () { if (điều kiện dừng) { ... //Trảvềgiátrịhay kết thúc công việc } //Thực hiện một sốcông việc (nếu có) . . .TenHam (); //Giải quyết vấn đềnhỏhơn //Thực hiện một sốcông việc (nếu có) . . . TenHam (); //Giải quyết vấn đềcòn lại //Thực hiện một sốcông việc (nếu có) } 6
Vídụ: Tính sốhạng thứn của dã y Fibonaci được định nghĩ a như sau: f1 = f0 =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); } 7
* * Trong thân của hàm có lời gọi hàm gọi lại chính nó được đặt bên trong vòng lặp. TenHam () { for (int i = 1; i
Vídụ: Tính sốhạng thứn của dã y {Xn} được định nghĩ 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; i
* *Trong thân của hàm này có lời gọi hàm đến hàm kia vàtrong thân của hàm kia có lời gọi hàm tới hàm này. 10
TenHam2 (); TenHam1 () { //Thực hiện một sốcông việc (nếu có) …TenHam2 (); //Thực hiện một sốcông việc (nếu có) } TenHam2 () { //Thực hiện một sốcông việc (nếu có) …TenHam1 (); //Thực hiện một sốcông việc (nếu có) } 11
Vídụ: Tính sốhạng thứn của hai dã y {Xn}, {Yn} được định nghĩ 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; return n*n*TinhXn(n-1) + TinhYn(n-1); } 12
* *Ví dụ tính n! với n=5 13