Bài 4 : Hàm(Function) Trong C (Phần 2)-Hàm Đệ Quy

1087

Bài trước chúng ta đã tìm hiểu về  cơ bản về  Hàm. Ở bài viết này chúng ta sẽ tìm hiểu phạm vi biến trong chương trình và tìm hiểu thế nào là hàm đệ quy?

Biến và Phạm vi của biến trong chương trình

  • Khi sử dụng biến, có 2 điều cần quan tâm
    • „ Phạm vi của biến (scope): biến khai báo trong hàm nào, chỉ có phạm vi họat động trong hàm đó, kể cả hàm main().
    • „ Đời sống của biến (life): đời sống là khoảng thời gian biến được khai báo cho đến khi được giải phóng khỏi bộ nhớ.
  • Chú ý
    • „ Các biến tòan cục được khai báo ngòai các hàm thì có phạm vi hoạt động trong tất cả các hàm trong file chương trình.
    • „ Một biến được cấp phát bộ nhớ khi hàm chứa biến đó được gọi, và sẽ bị giải phóng khỏi bộ nhớ khi kết thúc hàm, trừ các biến được khai báo static.

Khai báo biến tĩnh (static variables)

  • „ Biến tĩnh là biến mà nó không bị giải phóng khi chương trình con (ctc) chứa nó kết thúc
  • Có thể sử dụng biến tĩnh khi chúng ta cần giữ lại giá trị của biến trong 1 ctc khi ctc đó được gọi nhiều lần
  • Khai báo: thêm từ khóa static,
    •  static int a = 10;
    • „ static double b;
    • „ static long c;

Ví dụ : Sử dụng biến tĩnh

static

Hàm Đệ Quy

1.Mở đầu

C không những cho phép từ hàm này gọi tới hàm khác, mà nó còn cho phép từ một điểm trong thân của hàm gọi tới chính hàm đó. Hàm như vậy gọi là hàm đệ quy.

Khi hàm gọi đệ quy đến chính nó, thì mỗi lần gọi máy sẽ tạo ra một tập các biến cục bộ mới hoàn toàn độc lập với tập các biến cục bộ đã tạo ra trong các lần gọi trước.

Để minh họa chi tiết những điều trên, ta nên xét một ví dụ về tính giai thừa của số nguyên dương n. Khi  không dùng phương pháp đệ quy hàm có thể được viết như sau :

Ta nhận thấy rằng n! có thể tính theo công thức truy hồi sau:

            n!=1                             nếu n=0

    n!=n*(n-1)!                  nếu n>0

Hàm tính n! theo  phương pháp đệ quy có thể được viết như sau:

Ta đi giải thích hoạt động của hàm đệ quy khi sử dụng hàm main dưới đây:

Lần gọi đầu tiên tới hàm gtdq được thực hiện từ hàm main(). Máy sẽ tạo ra một tập các biến tự động của hàm gtdq. Tập này chỉ gồm các đối n.Ta gọi đối n được tạo ra lần thứ nhất là n thứ nhất. Giá trị của tham số thực (số 3) được gắn cho n thứ nhất. Lúc này biến n trong thân hàm được xem là n thứ nhất. Do n thứ nhất có giá trị bằng 3  nên điều kiện trong toán tử if là sai và do máy sẽ lựa chọn câu lệnh else. Theo câu lệnh này , máy tính sẽ tính giá trị của biểu thức :

n*gtdq(n-1)(*)

Để tính biểu thức trên, máy cần gọi chính hàm gtdq vì thế  lần gọi thứ hai sẽ được thực hiện. Máy sẽ tạo ra đối n mới, ta gọi đó là n thứ hai. Giá trị của n-1 ở đây lại là đối của hàm , được truyền cho hàm và hiểu là n thứ hai , do vậy  n thứ hai có giá trị là 2. Bây giờ, do n thứ hai vẫn chưa thoả mãn điều kiện if nên máy lại tiếp tục tính biểu thức :

n*gtdq(n-1) (**)

Biểu thức trên lại gọi hàm gtdq lần thứ ba. Máy lại tạo ra đối n lần thứ ba và ở đây n thứ ba có giá trị = 1. Đối n=1 thứ ba có giá trị bằng 1. Đối n = 1 thứ ba lại được truyền cho hàm, lúc này điều kiện trong if được thỏa mãn, máy đi thực hiện câu lệnh:

return 1=gtdq(1) (***)

Bắt đầu từ đây, máy sẽ thực hiện ba lần ra khỏi hàm gtdq. Lần ra khỏi hàm thứ nhất ứng với lần vào thứ ba. Kết quả là đối n thứ ba được giải phóng, hàm gtdq(1) cho giá trị là 1 và máy trở về xét giá trị của biểu thức

n*gtdq(1) đây là kết quả của (**)

ở đây, n là n thứ hai và có giá trị bằng 2. Theo câu lệnh return, máy sẽ thực hiện lần ra khỏi hàm lần thứ hai, đối n thứ hai sẽ được giải phóng, kết quả là biểu thức trong (**) có giá trị là 2.1. Sau đó máy trở về biểu thức (*) lúc này là :

n*gtdq(2)=n*2*1

n lại hiểu là thứ nhất, nó có giá trị bằng 3, do vậy giá trị của biểu thức trong (*) là 3.2.1=6. Chính giá trị này được sử dụng trong câu lệnh printf của hàm main() nên kết quả in ra trên màn hình là :

3!=6

Chú ý : Hàm đệ qui so với hàm có thể dùng vòng lặp thì đơn giản hơn, tuy nhiên với máy tính khi dùng hàm đệ qui sẽ dùng nhiều bộ nhớ trên ngăn xếp và có thể dẫn đến tràn ngăn xếp. Vì vậy khi gặp một bài toán mà có thể có cách giải lặp ( không dùng đệ qui ) thì ta nên dùng cách lặp này. Song vẫn tồn tại những bài toán chỉ có thể giải bằng đệ qui.

2. Các bài toán có thể dùng đệ quy

Phương pháp đệ qui thường áp dụng cho các bài toán phụ thuộc tham số có hai đặc điểm sau :

Bài toán dễ dàng giải quyết trong một số trường hợp riêng ứng với các giá trị đặc biệt của tham số. Người ta thường gọi là trường hợp suy biến.

Trong trường hợp tổng quát, bài toán có thể qui về một bài toán cùng dạng nhưng giá trị tham số thì bị thay đổi. Sau một số hữu hạn bước biến đổi dệ qui nó sẽ dẫn tới trường hợp suy biến.

Bài toán tính n giai thừa nêu trên thể hiện rõ nét đặc điểu này.

3. Cách xây dựng hàm đệ quy

Ví dụ :

4. Bộ tiền xử lý C

C đưa ra một số cách mở rộng ngôn ngữ bằng các bộ tiền sử lý macro đơn giản. Có hai cách mở rộng chính là #define mà ta đã học và khả năng bao hàm nội dung của các file khác vào file đang được dịch.

Bao hàm file

Để dễ dàng xử lý một tập các #define và khai báo ( trong các đối tượng khác ), C đưa ra cách bao hàm các file khác vào file đang dịch có dạng :

Dòng khai báo trên sẽ được thay thế bởi nội dung của file có tên là tên file. Thông thường có vài dòng như vậy xuất hiện tại đầu mỗi file gốc để gọi vào các câu lệnh #define chung và các khai báo cho các biến ngoài. Các #include được phép lồng nhau. Thường thì các #include được dùng nhiều trong các chương trình lớn, nó đảm bảo rằng mọi file gốc đều được cung cấp cùng các định nghĩa và khai báo biến, do vậy tránh được các lỗi khó chịu do việc thiếu các khai báo định nghĩa. Tất nhiên khi thay đổi file được bao hàm vào thì mọi file phụ thuộc vào nó đều phải dịch lại.

Phép thế MACRO

Định nghĩa có dạng :

sẽ gọi tới một macro để thay thế biểu thức 2 (nếu có) cho biểu thức 1.

Ví dụ :

Macro thay biến YES bởi giá trị 1 có nghĩa là hễ có chỗ nào trong chương trình có xuất hiện biến YES thì nó sẽ được thay bởi giá trị 1.

Phạm vi cho tên được định nghĩa bởi #define là từ điểm định nghĩa đến cuối file gốc. Có thể định nghĩa lại tên và một định nghĩa có thể sử dụng các định nghĩa khác trước đó. Phép thế không thực hiện cho các xâu dấu nháy, ví dụ như YES là tên được định nghĩa thì không có việc thay thế nào được thực hiện trong đoạn lệnh có “YES”.

Vì việc thiết lập #define là một bước chuẩn bị chứ không phải là một phần của chương trình biên dịch nên có rất ít hạn chế về văn phạm về việc phải định nghĩa cái gì. Chẳng hạn như những người lập trình ưa thích PASCAL có thể định nghĩa :

sau đó viết đoạn chương trình :

Ta cũng có thể định nghĩa các macro có đối, do vậy văn bản thay thế sẽ phụ thuộc vào cách gọi tới macro.

Ví dụ :

Định nghĩa macro gọi max như sau :

Việc sử dụng :

tương đương với :

Như vậy ta có thể có hàm tính cực đại viết trên một dòng. Chừng nào các đối còn giữ được tính nhất quán thì macro này vẫn có giá trị với mọi kiểu dữ liệu, không cần phải có các loại hàm max khác cho các kiểu dữ liệu khác nhưng vẫn phải có đối cho các hàm.

Tất nhiên nếu ta kiểm tra lại việc mở rộng của hàm max trên, ta sẽ thấy rằng nó có thể gây ra số bẫy. Biểu thức đã được tính lại hai lần và điều này là không tốt nếu nó gây ra hiệu quả phụ kiểu như các lời gọi hàm và toán tử tăng. Cần phải thận trọng dùng thêm dấu ngoặc để đảm bảo trật tự tính toán. Tuy vậy, macro vẫn rất có giá trị.

Không được viết dấu cách giữa tên macro với dấu mở ngoặc bao quanh danh sách đối.

Ví dụ :

Xét chương trình sau :

Chương trình sử dụng MACRO sẽ như sau :

BÌNH LUẬN

Please enter your comment!
Please enter your name here