Bài giảng Kỹ thuật lập trình - Chương 08: Hàm - Nguyễn Thanh Tùng

Nội dung text: Bài giảng Kỹ thuật lập trình - Chương 08: Hàm - Nguyễn Thanh Tùng

1. Hàm main và hàm thư viện • Cách truyền tham số dòng lệnh trong Visual Studio • (1) Nhấn chuột phải trên trong cửa sổ “Solution Explorer” • (2) Chọn “Debug” > “Command Arguments” • (3) Xổ chọn “Edit ” trong danh sách chức năng của “Command Arguments” • (4) Gõ vào danh sách thông số: các thông số cách nhau bởi khoảng trắng hay dấu “,” Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 14 © 2016
2. Hàm main và hàm thư viện ◼ Ví dụ hàm trong thư viện ◼ (1) Dùng chỉ thị #include để thông báo với bộ biên dịch là có sử dụng thư viện ◼ (2) Gọi các hàm cần thiết. Khi gọi một hàm chỉ cần biết ◼ Tên hàm + công dụng của hàm ◼ Các giá trị cần cung cấp cho hàm ◼ Giá trị trả về của hàm Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 16 © 2016
3. Sử dụng hàm tự tạo ◼ Gồm hai bước ◼ (1) Tạo ra hàm ◼ Mô tả một hàm ◼ Hiện thực hàm ◼ (2) Gọi hàm Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 18 © 2016
4. Sử dụng hàm tự tạo Định nghĩa hàm Phần thân của hàm, gồm: #include Gồm các câu lệnh được thực hiện cùng nhau, #include lần lượt. Ở ví dụ này: có 3 lệnh trong thân hàm int add(int a, int b) Dùng câu lệnh return để chấm dứt thực thi { hàm và trả điều khiển về cho hàm gọi → chuyển int c; thực thi về lệnh kế sau lệnh gọi hàm c = a + b; return c; } int main(){ printf("10 + 15 = %d", add(10, 15)); system("pause"); return EXIT_SUCCESS; } Các lệnh trong thân của hàm phải được gôm lại với nhau bằng cặp dấu “{“ và “}” Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 20 © 2016
5. Sử dụng hàm tự tạo Nguyên tắc thực thi khi gọi hàm ◼ Khi lời gọi hàm được thực thi thì bộ thực thi sẽ làm các công việc ◼ Lưu vết: lệnh kế tiếp của lệnh gọi hàm ◼ Copy các thông số cho hàm được gọi ◼ Làm các công việc hệ thống khác (chưa cần quan tâm cho người học lập trình C) ◼ Chuyển điều khiển thực thi cho hàm được gọi để nó thực thi lệnh đầu tiên trong hàm được gọi ◼ Hàm được gọi thực thi các lệnh ◼ Khi hàm được gọi thực hiện lệnh return. ◼ Giải phóng tất cả các biến cục bộ của nó ◼ Trả điều khiển về lệnh theo sau lệnh gọi hàm ◼ Hàm gọi giải phóng các thông số đã truyền và thực thi lệnh kế tiếp theo lệnh gọi hàm Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 22 © 2016
6. Tổ chức mã nguồn int add(int a, int b) Phần mô tả hàm (header) { int c; c = a + b; Phần thân hàm (body) return c; } Phần mô tả nên được tách riêng khỏi toàn bộ phần định nghĩa một hàm. Lý do: • Không cần quan tâm thứ tự các hàm trong mã nguồn. • Dùng lại các hàm trong dự án hoặc nhiều dự án • Phát triển thư viện các hàm → không cần chuyển giao cho bên thứ 3 (người mua thư viện) mã nguồn phần hiện thực các hàm Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 24 © 2016
7. Tổ chức mã nguồn ◼ Đưa phần mô tả vào một tập tin riêng ◼ Gọi là tập tin mô tả (header): *.h ◼ Có thể sử dụng lại ở nhiều tập tin khác trong dự án ◼ Sử dụng chỉ thị #if !defined(.) endif để tránh lỗi “định nghĩa lặp lại” (redefinition) ◼ Đưa phần hiện thực vào một tập tin riêng ◼ Gọi là tập tin hiện thực (implementation): *.c; *.cpp ◼ Có thể sử dụng lại ở nhiều tập tin khác trong dự án ◼ Đưa phần hiện thực vào một tập tin riêng ◼ Khai báo có sử dụng đến các hàm ở *.h nói trên ◼ Gọi hàm Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 26 © 2016
8. Tổ chức mã nguồn phụ thuộc Mô-đun phụ thuộc Mô tả các hàm (my_math.h) Mô-đun chương Mô-đun trình chính Hiện thực các hàm (program.cpp) (my_math.cpp) Sự phụ thuộc được biểu thi bởi chỉ thị #include ”my_math.h” trong mã nguồn Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 28 © 2016
9. Tổ chức mã nguồn Tập tin: ”my_math.h” #if !defined(MY_MATH_HEADER) MY_MATH_HEADER là một tên (danh #define MY_MATH_HEADER hiệu) int add(int a, int b); #endif Phần mô tả Nhờ chỉ thị #if mà phần mô tả của các tên như hàm cho hàm add ở đây không bị lặp lại nhiều lần khi được dùng ở add nhiều tập tin khác nhau, kể cả trong tập tin *.h Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 30 © 2016
10. Tổ chức mã nguồn Tập tin: ”program.cpp” #include #include #include "my_math.h" int main(){ printf("10 + 15 = %d", add(10, 15)); system("pause"); return EXIT_SUCCESS; } Khai báo sử dụng phần mô tả trong tập tin *.h (“my_math.h”) Lời gọi hàm (hàm add) Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 32 © 2016
11. Tổ chức mã nguồn ◼ Bài toán xây dựng các hàm tính tính toán cho số phức (Complex) ◼ Phân tích: ◼ Cần cung cấp kiểu dữ liệu cho số phức: z = x + y*i ◼ Cung cấp các hàm với kiểu mới này ◼ Hàm lấy giá trị độ lớn của số phức ◼ Hàm lấy giá trị góc của số phức Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 34 © 2016
12. Tổ chức mã nguồn ◼ Hàm lấy giá trị góc của số phức ◼ Cần định nghĩa các hằng ◼ PI ◼ Hằng biểu diễn giá trị không xác định “indeterminate” ◼ Cần định nghĩa macro để hổ trợ phép so sánh “==“ ◼ Hằng hổ trợ chuyển đổi từ RADIAN sang độ và ngược lại #define PI 3.14159265 #define UN_DEF_ANGLE (2*PI) #define EPSILON (1.0E-13) #define equal(d1, d2) (abs((d1) - (d2)) < EPSILON) #define RAD_2_DEG (180.0/PI) #define DEG_2_RAD (PI/180.0) Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 36 © 2016
13. Tổ chức mã nguồn phụ thuộc Mô-đun phụ thuộc Mô tả các hàm (complex.h) Mô-đun chương Mô-đun trình chính Hiện thực các hàm (program.cpp) (complex.cpp) Sự phụ thuộc được biểu thi bởi chỉ thị #include ”complex.h” trong mã nguồn Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 38 © 2016
14. Tổ chức mã nguồn Tập tin: complex.h #if !defined(MY_MATH_HEADER) #define MY_MATH_HEADER #define PI 3.14159265 #define UN_DEF_ANGLE (2*PI) #define EPSILON (1.0E-13) #define equal(d1, d2) (abs((d1) - (d2)) < EPSILON) #define RAD_2_DEG (180.0/PI) typedef struct{ double x, y; } Complex; double get_magnitude(Complex c); double get_angle(Complex c); void print_complex(Complex c); #endif Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 40 © 2016
15. Thuộc tập tin: complex.cpp double get_angle(Complex c){ Tổ chứcdouble mãangle; nguồn if(c.x > 0){ angle = atan(c.y/c.x); } if((c.x = 0)){ angle = atan(c.y/c.x) + PI; } if((c.x 0)){ Hàm lấy góc của số phức angle = PI/2; } if(equal(c.x, 0.0) && (c.y < 0)){ angle = -PI/2; } if(equal(c.x, 0.0) && equal(c.y, 0.0)){ angle = UN_DEF_ANGLE; } angle *= RAD_2_DEG; Trường ĐạireturnHọc Bách Khoaangle; Lập trình C/C++ }Trung Tâm Kỹ Thuật Điện Toán 42 © 2016
16. Các kiểu truyền tham số Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 44 © 2016
17. Các kiểu truyền tham số ◼ Có hai kiểu truyền tham số ◼ Truyền tham số bằng trị hay truyền bằng trị ◼ Truyền tham số bằng con trỏ truyền bằng con trỏ, truyền bằng địa chỉ Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 46 © 2016
18. Các kiểu truyền tham số Cách nhận biết hai kiểu truyền Dấu sao (*) chỉ ra thông số nào sẽ được truyền bằng địa chỉ void swap(int a, int b){ } a và b sẽ được truyền bằng trị void swap(int *a, int *b){ } a và b sẽ được truyền bằng địa chỉ Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 48 © 2016
19. Các kiểu truyền tham số Lời gọi hàm: truyền bằng trị #include #include void swap(int a, int b){ Hàm swap hoán đổi giá trị của hai int t = a; biến a và b qua biến tạm t a = b; b = t; Lời gọi hàm: truyền x và y là đối sô } tương ứng cho a và b int main(){ int x = 10, y = 100; printf("Truoc khi goi ham swap(x,y)\n"); printf("x = %3d; y = %3d\n", x, y); swap(x, y); printf("Truoc khi goi ham swap(x,y)\n"); printf("x = %3d; y = %3d\n", x, y); printf("\n\n"); system("pause"); return EXIT_SUCCESS; } Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 50 © 2016
20. Các kiểu truyền tham số Lời gọi hàm: truyền bằng trị void swap(int a, int b){ a : 10 b : 100 int t = a; a = b; b = t; } COPY giá trị int main(){ int x = 10, y = 100; swap(x, y); x : 10 y : 100 return EXIT_SUCCESS; } Lời gọi hàm swap(x, y) trong main khiến cho biến a và b của giữ giá trị của x và y tương ứng; nghĩa là 10 và 100 Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 52 © 2016
21. Các kiểu truyền tham số Lời gọi hàm: truyền bằng địa chỉ void swap(int a, int b){ a : 100 b : 100 int t = a; a = b; b = t; t : 10 } int main(){ int x = 10, y = 100; swap(x, y); x : 10 y : 100 return EXIT_SUCCESS; } a = b; Khiến cho biến a có có trị của b nghĩa là 100 Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 54 © 2016
22. Các kiểu truyền tham số Lời gọi hàm: truyền bằng địa chỉ void swap(int a, int b){ a : 100 b : 10 int t = a; a = b; b = t; t : 10 } int main(){ int x = 10, y = 100; swap(x, y); x : 10 y : 100 return EXIT_SUCCESS; } swap(int a, int b) Hoàn tất hoán đổi giá trị a và b, không chạm gì đến x và y ở hàm main. Do đó, khi nó kết thúc hai biến x và y trong main vẫn giữ nguyên giá trị Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 56 © 2016
23. Các kiểu truyền tham số Hàm swap hoán đổi giá trị của hai đối số được truyền cho a và b Lời gọi hàm: truyền bằng địa chỉ tương ứng. #include Toán tử sao (*): #include a là địa chỉ → (*a) là giá trị của void swap(int *a, int *b){ int t = *a; vùng nhớ có địa chỉ là a *a = *b; *b = t; Lời gọi hàm: truyền địa chỉ của } biến x và y vào hai thông số a và b int main(){ tương ứng. int x = 10, y = 100; Dùng toán tử &: để lấy địa chỉ printf("Truoc khi goi ham swap(x,y)\n"); printf("x = %3d; y = %3d\n", x, y); swap(&x, &y); printf("Truoc khi goi ham swap(x,y)\n"); printf("x = %3d; y = %3d\n", x, y); printf("\n\n"); system("pause"); return EXIT_SUCCESS; } Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 58 © 2016
24. Các kiểu truyền tham số Lời gọi hàm: truyền bằng địa chỉ void swap(int *a, int *b){ a : b : int t = *a; *a = *b; *b = t; } int main(){ int x = 10, y = 100; swap(&x, &y); x : 10 y : 100 return EXIT_SUCCESS; } Lời gọi hàm swap(&x, &y) trong main khiến cho biến a và b của hàm swap(int *a, int *b) chứa địa chỉ của x và y tương ứng Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 60 © 2016
25. Các kiểu truyền tham số Lời gọi hàm: truyền bằng địa chỉ void swap(int *a, int *b){ a : b : int t = *a; *a = *b; *b = t; t : 10 } int main(){ int x = 10, y = 100; swap(&x, &y); x : 100 y : 100 return EXIT_SUCCESS; } *a = *b; khiến cho giá trị của ô nhớ có địa chỉ là b được gán vào giá trị của ô nhớ có địa chỉ a; nghĩa là biến y được gán vào x Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 62 © 2016
26. Các kiểu truyền tham số Lời gọi hàm: truyền bằng địa chỉ void swap(int *a, int *b){ a : b : int t = *a; *a = *b; *b = t; t : 10 } int main(){ int x = 10, y = 100; swap(&x, &y); x : 100 y : 10 return EXIT_SUCCESS; } *b = t; khiến cho giá trị của biến t được COPY vào ô nhớ có địa chỉ là b; tương đương, biến y được gán giá trị t (nghĩa là 10) Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 64 © 2016
27. Hàm và mảng, con trỏ Lưu ý: Mảng và con trỏ đề là những ô nhớ chứa địa chỉ Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 66 © 2016
28. Hàm và mảng, con trỏ ◼ Sử dụng hàm để xử lý mảng, cần truyền vào hàm ◼ Ví dụ: ◼ Viết hàm để in ra các phần tử của mảng ◼ Phân tích ◼ (1) Cần truyền mảng giá trị ◼ (2) Cần truyền số lượng phần tử của mảng Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 68 © 2016
29. Hàm và mảng, con trỏ Lời gọi hàm: • Thông số thứ 1: a Truyền địa chỉ của phần tử đầu tiên vào hàm ◼ Cú pháp khai báo thông số (truyền bằng địa chỉ) #include • Thông số thứ 2: size #include Truyền bằng trị #define MAX_SIZE 100 void print_array1(int arr[MAX_SIZE], int size){} void print_array2(int arr[], int size){} void print_array3(int *ptr, int size){} int main(){ int size = 5; int a[MAX_SIZE]; for(int i=0; i<size; i++) a[i] = i*i; print_array1(a, size); print_array2(a, size); print_array3(a, size); return EXIT_SUCCESS; Trường Đại Học Bách Khoa Lập trình C/C++ }Trung Tâm Kỹ Thuật Điện Toán 70 © 2016
30. Hàm và mảng, con trỏ ◼ Tương tự, thì hàm in các mảng có kiểu Student và Point3D có thể có cú pháp: void print_array1(Student arr[MAX_SIZE], int size); void print_array2(Student arr[], int size); void print_array3(Student *arr, int size); void print_array1(Point3D arr[MAX_SIZE], int size); void print_array2(Point3D arr[], int size); void print_array3(Point3D *arr, int size); Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 72 © 2016
31. Hàm và mảng, con trỏ Không cho phép hàm thay đổi phần tử trên mảng ◼ Sử dụng từ khoá const trước tên kiểu phần tử Đã khai báo const + cố tình thay đổi phần tử trên mảng thì có lỗi Lỗi: “expression must be a modifiable lvalue” Nghĩa: arr không được dùng trong bên trái của biểu thức gán Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 74 © 2016
32. Hàm inline ◼ Tác dụng của hàm inline ◼ Hàm không inline ◼ Tốn chi phí thực thi khi gọi hàm ◼ COPY các tham số ◼ Lưu trữ các thanh ghi ◼ Phục hồi các thanh ghi ◼ Giải phóng các tham số ◼ V.v Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 76 © 2016
33. Con trỏ hàm ◼ Con trỏ hàm là gì? ◼ Ứng dụng của con trỏ hàm ◼ Khai báo con trỏ hàm ◼ Gọi hàm thông qua con trỏ ◼ Định nghĩa kiểu dữ liệu con trỏ hàm ◼ Truyền con trỏ hàm như thông số của hàm ◼ Mảng con trỏ hàm Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 78 © 2016
34. Con trỏ hàm Ứng dụng của con trỏ hàm ◼ Khi không có con trỏ hàm ◼ Hàm được gọi thông qua tên hàm trong mã nguồn ◼ ➔ Cần biết trước tên hàm tại thời điểm biên dịch ◼ Khi dùng con trỏ hàm ◼ Có thể gọi hàm qua con trỏ đến hàm ◼ ➔ Không cần biết trước tên hàm tại thời điểm biên dịch ◼ ➔ Chỉ cần biết địa chỉ hàm tại thời điểm thực thi và gọi nó ◼ ➔ Chương trình uyển chuyển hơn Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 80 © 2016
35. Con trỏ hàm Ứng dụng của con trỏ hàm ◼ Ví dụ: Xây dựng thư viện mà hàm để làm công việc nào đó chỉ có thể biết ở thời điểm tương lai, theo mỗi dự án. ◼ Hàm xử lý sự kiện trong thư viện phát triển ứng dụng co giao diện đồ hoạ ◼ Hàm callback ◼ Ví dụ: Để hiện thực bảng hàm trong ngôn ngữ C++ Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 82 © 2016
36. Con trỏ hàm Khai báo con trỏ hàm – ví dụ typedef struct{ Student: char code[5]; Kiểu dữ liệu chứa thông tin sinh viên char name[20]; float gpa; } Student; print_one_row: void print_one_row(Student student); Một hàm trả về void, đầu vào là void (*print_ptr1)(Student); một Student void (*print_ptr2)(Student) = NULL; void (*print_ptr3)(Student) = print_one_row; print_ptr1, print_ptr2, print_ptr3: • là các biến con trỏ hàm (là các biến chứa địa chỉ của hàm). Các hàm có thể gán cho nó là (không cần quan tâm tên) • Trả về void, không trả về • Một thông số đầu vào có kiểu là Student Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 84 © 2016
37. Con trỏ hàm Gọi hàm qua con trỏ Hàm main int main(){ void (*print_ptr3)(Student) = print_one_row; Student s = {"001", "Nguyen Thanh An", 9.8f}; Lời gọi hàm qua con trỏ: print_ptr3(s); địa chỉ hàm ở vị trí tên hàm thông thường trong lời gọi (*print_ptr3)(s); hàm thông thường system("pause"); return EXIT_SUCCESS; } Lời gọi hàm qua con trỏ: dùng đến toán tử * Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 86 © 2016
38. Con trỏ hàm Định nghĩa kiểu dữ liệu con trỏ hàm typedef struct{ char code[5]; char name[20]; float gpa; } Student; typedef void (*PrintStudentPtr)(Student); Từ khoá typedef giúp rút ngắn việc khai báo biến PrintStudentPtr: có thể được sử dụng như tên kiểu mới Nó là họ các hàm có kiểu trả về void, chấp nhận 1 thông số đầu vào có kiểu Student Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 88 © 2016
39. Con trỏ hàm Định nghĩa kiểu dữ liệu con trỏ hàm Ví dụ hoàn chỉnh #include #include typedef struct{ char code[5]; char name[20]; float gpa; } Student; typedef void (*PrintStudentPtr)(Student); void print_one_row(Student student); void print_one_row(Student student){ printf("%-6s%-20s%-4.1f\n", student.code, student.name, student.gpa); } Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 90 © 2016
40. Con trỏ hàm Truyền con trỏ như tham số - khai báo thông số void print_list1(Student *list, int size, PrintStudentPtr print_ptr); void print_list2(Student *list, int size, void (*print_ptr)(Student)); Không dùng tên kiểu Dùng tên kiểu đã định nghĩa bằng typedef Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 92 © 2016
41. Con trỏ hàm Truyền con trỏ như tham số - dùng thông số #include #include typedef struct{ char code[5]; char name[20]; float gpa; } Student; typedef void (*PrintStudentPtr)(Student); void print_one_row(Student student); void print_list1(Student *list, int size, PrintStudentPtr print_ptr); void print_list2(Student *list, int size, void (*print_ptr)(Student)); Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 94 © 2016
42. Con trỏ hàm Truyền con trỏ như tham số - dùng thông số Kết quả xuất ra màn hình Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 96 © 2016
43. Hàm đệ quy ◼ Hàm đệ quy là hàm gọi lại chính nó ◼ Trực tiếp: ◼ foo() gọi foo() trực tiếp trong thân hàm foo() ◼ Gán tiếp: ◼ foo() gọi bar, bar gọi foo(); hoặc qua nhiều trung gian hàm khác Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 98 © 2016
44. Hàm đệ quy ◼ Ví dụ ◼ Chương trình tính giai thừa: 1x2x3x x N ◼ Hàm giai_thua(N) gọi lại giai_thua(N-1) long long giai_thua(int N){ int ket_qua; if(N <=1) ket_qua = 1; else ket_qua = N*giai_thua(N-1); return ket_qua; } Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 100 © 2016
45. Hàm đệ quy ◼ Yêu cầu cần thiết của một hàm đệ quy: ◼ Điều kiện dừng quá trình gọi đệ quy ◼ Ví dụ: long long giai_thua(int N){ if(N <=1) ket_qua = 1; Dừng quá trình gọi đệ quy } Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 102 © 2016
46. Hàm đệ quy ◼ Giải bài toán bằng đệ quy ◼ Lời giải của bài toán có kích thước N được tổng hợp từ lời giải của các bài toán có kích thước nhỏ hơn. ◼ Ví dụ: ◼ Lời giải cho bài toán tìm tổng N phần tử ◼ Giả sử ta biết tổng của (N-1) phần tử ◼ Vậy, lời giải của N phần tử được tổng hơp như thế nào từ kết quả trên? Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 104 © 2016
47. Hàm đệ quy ◼ Giải bài toán bằng đệ quy ◼ Lời giải của bài toán có kích thước N được tổng hợp từ lời giải của các bài toán có kích thước nhỏ hơn. ◼ Ví dụ: ◼ Tìm số thứ N trong dãy số Fibonaci ◼ F(1) = 1 ◼ F(2) = 1 ◼ N >2: F(N) = F(N-1) + F(N-2) ◼ Lời giải ◼ Giả sử ta có F(N-1) và F(N-2) ◼ Lời giải cho F(N) được tổng hợp như thế nào từ các kết quả trên? Trường Đại Học Bách Khoa Lập trình C/C++ Trung Tâm Kỹ Thuật Điện Toán 106 © 2016