Chương 4. Hàm

Đơn vị cơ bản giúp tái sử dụng mã nguồn, giảm thiểu trùng lặp và tổ chức chương trình theo cấu trúc khoa học, linh hoạt.

---

1. Lập trình hàm

1.1. Giới thiệu về hàm

1.1.1. Khái niệm

Hàm trong $\texttt{C++}$ là một khối lệnh có thể tái sử dụng, được thiết kế để thực hiện một chức năng cụ thể trong chương trình. Hàm có thể nhận đầu vào (tham số) và trả về kết quả (giá trị trả về).

1.1.2. Lợi ích của hàm

• Giảm lặp mã: Code được gom vào một nơi, không phải viết lại nhiều lần.
• Dễ đọc – dễ quản lý: Chương trình rõ ràng hơn nhờ chia thành các phần nhỏ.
• Tái sử dụng: Một hàm có thể dùng ở nhiều nơi hoặc nhiều chương trình khác nhau.
• Dễ bảo trì: Khi cần sửa logic, chỉ sửa trong hàm thay vì toàn bộ chương trình.
• Hỗ trợ chia bài toán lớn thành các phần nhỏ: Giúp lập trình có cấu trúc và dễ phát triển.

---

1.2. Cấu trúc và sử dụng hàm

1.2.1. Định nghĩa hàm

Cú pháp:

<kiểu trả về> <tên hàm>(<danh sách tham số>) {
    <các câu lệnh>
    return <giá trị trả về>;
}

Trong đó:

• <kiểu trả về>: Kiểu dữ liệu C/C++ (không trả về thì kiểu là void)
• <tên hàm>: Như quy tắc đặt tên định danh
• <danh sách tham số>: Như khi khai báo các biến trên một dòng, cách nhau bằng dấu “,”
• <giá trị trả về>: Kết quả trả về của hàm (phải cùng kiểu với <kiểu_trả_về>)

Ví dụ:

void chaoHoi() {
    cout << "Xin chào!" << endl;
}

int tong(int a, int b) {
    return a + b;
}

bool laNguyenTo(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

int giaiThua(int n) {
    int kq = 1;
    for (int i = 2; i <= n; i++) kq *= i;
    return kq;
}

---

1.2.2. Khai báo hàm và nguyên mẫu hàm

Khai báo hàm: Một khai báo hàm thông báo cho trình biên dịch về tên hàm và cách gọi của hàm. Phần thân hàm có thể định nghĩa sau.

int so_lon(int a, int b);

Nguyên mẫu hàm (Function Prototype): Là khai báo hàm nhưng không ghi tên tham số, chỉ ghi kiểu dữ liệu tham số.

int so_lon(int, int);

---

1.2.3. Gọi hàm

Gọi hàm (Function Call) là sử dụng tên hàm kèm tham số để thực thi thân hàm. Khi gọi hàm, chương trình nhảy vào thân hàm, thực hiện các lệnh, rồi trả về giá trị (nếu có).

Cú pháp:

<tên hàm>(<danh sách đối số>);

Ví dụ:

#include <iostream>
using namespace std;

int tong(int a, int b) {
    return a + b;
}

void chaoHoi() {
    cout << "Xin chào!\n";
}

int main(){
    int kq = tong(3, 5); // Gọi hàm có trả về giá trị
    cout << kq << endl;
    chaoHoi(); // Gọi hàm không trả về giá trị
    return 0;
}

Ghi chú:

• Hàm có trả về giá trị $\to$ dùng giá trị trả về hoặc gán cho biến.
• Hàm không trả về giá trị $\to$ chỉ gọi để thực hiện các lệnh bên trong.

---

1.2.4. Tham số và đối số

Tham số (Parameter) là biến được khai báo trong phần định nghĩa hàm, đóng vai trò "nhận dữ liệu" khi hàm được gọi.

Đối số (Argument) là giá trị thực tế được truyền vào hàm khi gọi hàm, đối số được gán cho tham số tương ứng.

Ví dụ:

int tong(int a, int b) { // a, b là tham số
    return a + b;
}

int main() {
    int x = 10, y = 20;
    tong(x, y);           // x, y là đối số
}

---

1.2.5. Giá trị trả về

Giá trị trả về của hàm là kết quả mà hàm gửi lại cho nơi gọi nó, được thực hiện bằng lệnh return. Khi chương trình gặp return, hàm sẽ kết thúc ngay lập tức và gửi giá trị sau return về cho lời gọi hàm. Giá trị sau return phải khớp với kiểu trả về của hàm. Riêng hàm không trả về gì thì dùng void.

Ví dụ:

#include <iostream>
using namespace std;

double binhPhuong(double x){
    return x * x; // Trả về giá trị
}

void chao() {
    cout << "Xin chào!\n"; // Không trả về giá trị
}

int main(){
    double kq = binhPhuong(5); // kq = 25
}

---

1.3. Phạm vi và mở rộng hàm

1.3.1. Phạm vi hoạt động của biến trong hàm

Trong $\texttt{C++}$, các biến có phạm vi hoạt động khác nhau tùy thuộc vào vị trí và cách biến được khai báo. Dưới đây là các loại phạm vi biến trong hàm:

• Biến cục bộ (Local Variable)
• Biến tĩnh cục bộ (Static Local Variable)
• Biến toàn cục (Global Variable)

1.3.1.1. Biến cục bộ

Biến cục bộ (Local Variable) được khai báo trong một khối ngoặc nhọn { }. Biến chỉ có tác dụng trong khối ngoặc nhọn đó và sẽ bị xóa khỏi bộ nhớ khi chương trình chạy ra khỏi khối.

Ví dụ:

#include <iostream>
using namespace std;

void demo() {
    int a = 5; // a là biến cục bộ, chỉ tồn tại trong demo()
    cout << "a trong demo: " << a << endl;
}

int main() {
    demo();
    // cout << a; // Lỗi: không dùng được a ở ngoài hàm demo
    int a = 10; // a trong main là một biến cục bộ khác, chỉ tồn tại trong main()
    cout << "a trong main: " << a << endl;
}

1.3.1.2. Biến tĩnh cục bộ

Biến tĩnh cục bộ (Static Local Variable): Khác với biến cục bộ thông thường, biến tĩnh cục bộ không bị hủy khi hàm kết thúc mà tồn tại suốt thời gian chạy của chương trình. Giá trị của biến tĩnh cục bộ được bảo lưu giữa các lần gọi hàm.

Ví dụ:

#include <iostream>
using namespace std;

void demGoiHam() {
    static int cnt = 0; // biến tĩnh cục bộ
    cnt++; // giữ nguyên giá trị giữa các lần gọi
    cout << "So lan goi ham: " << cnt << endl;
}

int main() {
    demGoiHam(); // 1
    demGoiHam(); // 2
    demGoiHam(); // 3
}

1.3.1.3. Biến toàn cục

• Biến toàn cục (Global variable): Biến toàn cục chỉ bị xóa khi chương trình kết thúc $\to$ Tốn bộn nhớ nếu lạm dụng
• Biến toàn cục có thể được/bị thay đổi bởi bất kỳ hàm nào $\to$ Dễ gây lỗi logic nếu dùng bất cẩn $\to$ Khi dùng hàm nên hạn chế dùng biến toàn cục

Ví dụ:

#include <iostream>
using namespace std;

int g = 0; // biến toàn cục, dùng được ở mọi hàm

void tang() {
    g++; // thay đổi giá trị biến toàn cục
}

int main() {
    cout << g << endl; // 0
    tang();
    cout << g << endl; // 1
    tang();
    cout << g << endl; // 2
}

---

1.3.2. Hàm trùng tên

Nạp chồng hàm (Function Overloading) là kỹ thuật cho phép nhiều hàm cùng tên nhưng khác nhau về danh sách tham số (số lượng hoặc kiểu dữ liệu). Trình biên dịch sẽ tự chọn đúng hàm dựa trên đối số khi gọi.

Ví dụ:

#include <iostream>
using namespace std;

// Hàm trùng tên: cùng tên 'tong', khác tham số
int tong(int a, int b) { // 2 tham số int
    return a + b;
}

double tong(double a, double b) { // 2 tham số double
    return a + b;
}

int tong(int a, int b, int c) { // 3 tham số int
    return a + b + c;
}

int main() {
    cout << tong(3, 5) << endl; // gọi int tong(int, int)
    cout << tong(2.5, 3.1) << endl; // gọi double tong(double, double)
    cout << tong(1, 2, 3) << endl; // gọi int tong(int, int, int)
}

---

2. Hàm đệ quy

2.1. Giới thiệu đệ quy

2.1.1. Khái niệm đệ quy

Đệ quy là cách giải một bài toán bằng cách chia bài toán lớn thành các bài toán nhỏ hơn nhưng có cùng cấu trúc. Mỗi bài toán nhỏ lại được xử lý theo đúng quy tắc của bài toán gốc. Quá trình này lặp lại cho đến khi đạt đến một trường hợp đơn giản nhất, gọi là điểm dừng, nơi không cần chia nhỏ nữa.

---

2.1.2. Nguyên tắc hoạt động của hàm đệ quy

Hàm đệ quy hoạt động theo nguyên tắc tự gọi lại chính nó để xử lý phiên bản nhỏ hơn của bài toán, và kết quả cuối cùng được hình thành khi các lời gọi quay ngược lại (unwinding). Quá trình này gồm ba bước quan trọng:

• Xác định điểm dừng (base case): Đây là trường hợp đơn giản nhất mà hàm không gọi lại chính nó nữa. Điểm dừng giúp kết thúc quá trình đệ quy và ngăn việc gọi vô hạn.
• Chia bài toán thành bài toán nhỏ hơn: Hàm xử lý bài toán lớn bằng cách tách nó thành phiên bản nhỏ hơn của chính nó. Mỗi lần gọi phải làm bài toán nhỏ đi, tiến gần đến điểm dừng.
• Quay lui kết quả (return ngược): Khi đạt đến điểm dừng, hàm bắt đầu trả kết quả ngược về các lời gọi trước đó. Các mức gọi được xếp chồng (stack) và được giải quyết theo thứ tự ngược lại.

Ví dụ: Tính giai thừa $5!$

Hàm đệ quy

int giaiThua(int n) {
    if (n == 1) return 1; // điểm dừng
    return n * giaiThua(n-1); // gọi lại chính nó
}

Sơ đồ hoạt động:

---

2.2. Cấu trúc và phân loại hàm đệ quy

2.2.1. Khái niệm và cấu trúc hàm đệ quy

Hàm đệ quy là một hàm trong lập trình tự gọi lại chính nó để giải quyết một bài toán. Mỗi lần gọi, hàm xử lý một phiên bản nhỏ hơn của bài toán gốc, và quá trình lặp lại cho đến khi đạt điểm dừng (base case), nơi hàm không gọi lại nữa.

Cấu trúc chung của hàm đệ quy:

<kiểu dữ liệu> <tên hàm>(<tham số>) {
    if (<điều kiện dừng>) return <giá trị>; // base case
    return <kết quả từ lời gọi chính nó>; // gọi lại chính hàm
}

Trong đó:

• <điều kiện dừng> (base case): Là điều kiện đơn giản nhất, giúp hàm kết >thúc và tránh gọi vô hạn
• <lời gọi đệ quy> (recursive call): Xử lý phiên bản nhỏ hơn của bài toán, tiến gần đến base case

---

2.2.2. Các loại đệ quy

Phân loại hàm đệ quy:

• Đệ quy tuyến tính (Single Recursion): 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.
• Đệ quy nhị phân (Binary Recursion): Trong thân hàm có hai lời gọi hàm gọi lại chính nó một cách tường minh.
• Đệ quy phi tuyến (Multiple Recursion): Trong thân hàm có từ hai lời gọi đệ quy trở lên (bao gồm cả đệ quy nhị phân).
• Đệ quy hỗ tương (Mutual Recursion): Trong thân hàm này có lời gọi hàm tới hàm kia và bên trong thân hàm kia có lời gọi hàm tới hàm này.

2.2.2.1. Đệ quy tuyến tính

Cấu trúc chương trình

<kieu_du_lieu> tenHam(<tham_so>) {
    // Bước 1: Điều kiện dừng (base case)
    if (<dieu_kien_ket_thuc>) {
        return <gia_tri_tra_ve>;
    }

    // Bước 2: Gọi đệ quy đúng 1 lần
    return <bieu_thuc_ket_hop> + tenHam(<tham_so_thay_doi>);
}

Ví dụ: Tính tổng từ 1 đến n

#include <iostream>
using namespace std;

// Hàm đệ quy tuyến tính tính tổng từ 1 đến n
int tinhTong(int n) {
    // Điều kiện dừng
    if (n == 1) {
        return 1;
    }

    // Gọi đệ quy duy nhất
    return n + tinhTong(n - 1);
}

int main() {
    int n;
    cout << "Nhap n: ";
    cin >> n;
    int ketQua = tinhTong(n);
    cout << "Tong tu 1 den " << n << " = " << ketQua << endl;
    return 0;
}

2.2.2.2. Đệ quy nhị phân

Cấu trúc chương trình:

<kieu_du_lieu> tenHam(<tham_so>) {
    // Điều kiện dừng (base case)
    if (<dieu_kien_ket_thuc>) {
        return <gia_tri>;
    }

    // Hai lời gọi đệ quy tường minh
    return tenHam(<tham_so_thay_doi_1>) + tenHam(<tham_so_thay_doi_2>);
}

Ví dụ: Tính số Fibonacci thứ n

#include <iostream>
using namespace std;

// Hàm đệ quy nhị phân tính số Fibonacci thứ n
int fibonacci(int n) {
    // Điều kiện dừng
    if (n == 0 || n == 1) {
        return n;
    }
    
    // Hai lời gọi đệ quy tường minh
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n;
    cout << "Nhap n: ";
    cin >> n;

    int ketQua = fibonacci(n);
    cout << "Fibonacci thu " << n << " = " << ketQua << endl;

    return 0;
}

2.2.2.3. Đệ quy phi tuyến

Cấu trúc chương trình:

<kieu_du_lieu> tenHam(<tham_so>) {
    // Điều kiện dừng (base case)
    if (<dieu_kien_ket_thuc>) {
        return <gia_tri>;
    } 
    
    <kieu_du_lieu> ketQua = <gia_tri_khoi_tao>;
    
    // Lời gọi đệ quy nằm trong vòng lặp
    for (<khoi_tao>; <dieu_kien_lap>; <cap_nhat>) {
        ketQua += tenHam(<tham_so_thay_doi>);
    }

    return ketQua;
}

Ví dụ: Đếm số cách viết n thành tổng của 1 và 2

#include <iostream>
using namespace std;

// Hàm đệ quy phi tuyến
int demCach(int n) {
    // Điều kiện dừng
    if (n == 0) return 1;
    if (n < 0) return 0;
    
    int soCach = 0;
 
    // Vòng lặp sinh lựa chọn (1 hoặc 2)
    for (int buoc = 1; buoc <= 2; buoc++) {
        soCach += demCach(n - buoc); // lời gọi đệ quy nằm trong vòng lặp
    }

    return soCach;
}

int main() {
    int n;
    cout << "Nhap n: ";
    cin >> n;

    cout << "So cach bieu dien " << n << " thanh tong cua 1 va 2 la: ";
    cout << demCach(n) << endl;

    return 0;
}

2.2.2.4. Đệ quy hỗ tương

Cấu trúc chương trình:

<kieu_du_lieu> hamA(<tham_so>) {
    // Điều kiện dừng
    if (<dieu_kien_ket_thuc_A>) {
        return <gia_tri>;
    }
    
    // Gọi sang hàm B
    return hamB(<tham_so_thay_doi>);
}

<kieu_du_lieu> hamB(<tham_so>) {
    // Điều kiện dừng
    if (<dieu_kien_ket_thuc_B>) {
        return <gia_tri>;
    }
    
    // Gọi ngược lại hàm A
    return hamA(<tham_so_thay_doi>);
}

Ví dụ: Kiểm tra số chẵn lẻ bằng đệ quy hỗ tương

#include <iostream>
using namespace std;

bool laChan(int n); // nguyên mẫu hàm
bool laLe(int n); // nguyên mẫu hàm

// Hàm kiểm tra số chẵn
bool laChan(int n) {
    if (n == 0) return true; // base case
    return laLe(n - 1); // gọi sang hàm laLe
}

// Hàm kiểm tra số lẻ
bool laLe(int n) {
    if (n == 0) return false; // base case
    return laChan(n - 1); // gọi ngược về laChan
}

int main() {
    int n;
    cout << "Nhap n: ";
    cin >> n;

    if (laChan(n)) cout << n << " la so chan\n";
    else cout << n << " la so le\n";

    return 0;
}

---

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

2.3.1. Các bước xây dựng hàm đệ quy

---

2.3.2. Sai lầm thường gặp khi viết đệ quy

Thiếu điều kiện dừng

Mô tả: Hàm không có base case -> gọi vô hạn -> tràn bộ nhớ.

Ví dụ sai:

int f(int n) {
    return f(n - 1) + 1; // không có base case
}

Truyền tham số sai

Mô tả: Hàm không giảm đúng biến -> kết quả sai.

Ví dụ sai:

int giaiThua(int n) {
    if (n == 0) return 1;
    return n * giaiThua(n); // phải là n-1
}

Gọi hàm đệ quy dư thừa

Mô tả: Lạm dụng đệ quy cho một số bài toán có thể phải tính toán lại các kết quả giống nhau, làm chậm chương trình.

Ví dụ sai:

int fib(int n) {
    if (n == 0 || n == 1) return n;
    return fib(n-1) + fib(n-2); // nhiều lời gọi trùng nhau
}

Lạm dụng đệ quy

Mô tả: Một số bài toán có thể xử lý bằng vòng lặp hoặc các kỹ thuật đơn giản, hiệu quả thay vì sử dụng đệ quy.

Ví dụ sai:

int tong(int n) {
    if (n == 0) return 0;
    return n + tong(n-1); // có thể dùng vòng lặp for dễ hơn
}

---

Tài liệu tham khảo

1. UIT - Hàm
2. UIT - Đệ quy