Hàm trong C++

Hàm

• Hàm giúp chia bài toán phức tạp thành các bài toán nhỏ hơn, dễ quản lý hơn.
• Hàm tách khái niệm khỏi cài đặt, giúp chương trình dễ hiểu và tái sử dụng code.
• Lập trình có cấu trúc sử dụng hàm để tránh lặp code.

Phân Loại Hàm

• Internal: Hàm do người dùng tự định nghĩa
• External: Hàm được nhóm thành các thư viện (ví dụ: abs, sqrt, exp trong math, iostream, stdlib).

Input/output

• Hàm nhận tham số đầu vào và trả về một giá trị.

Định Nghĩa và Khai Báo Hàm

• Hàm đặt sau main() cần khai báo prototype trước.
• Hàm đặt trước main() không cần prototype.
• Cú pháp định nghĩa hàm: <return type> <function name>(<parameter list>) { <local declarations> <sequence of statements> }.
• Cú pháp khai báo prototype hàm: <return type> <function name>(<parameter list>);.

Truyền Tham Số

• Pass-by-value: Giá trị của tham số được sao chép vào hàm
• Pass-by-reference: Tham số là một tham chiếu đến biến gốc

CPU và Bộ Nhớ

• CPU tính toán trên dữ liệu được lưu trữ trong các thanh ghi.
• Dữ liệu được chuyển giữa bộ nhớ và các thanh ghi.
• Kích thước mỗi ô nhớ là 8 bit, tương đương với 1 byte.
• Dữ liệu lớn hơn cần một chuỗi byte liên tiếp, xác định bởi địa chỉ byte đầu tiên và kích thước.

Bit và Giá Trị Dữ Liệu

• Big-endian: Thứ tự byte từ trái sang phải, địa chỉ byte tăng dần (ví dụ: mainframe, IPv4).
• Little-endian: Thứ tự byte từ trái sang phải, địa chỉ byte giảm dần (ví dụ: Intel x86, x86-64).
• Thứ tự byte mã hóa và giải mã cần nhất quán.

Bộ Nhớ Ảo

• Mỗi tiến trình được cấp một không gian bộ nhớ riêng.
• Hệ điều hành ánh xạ bộ nhớ logic với bộ nhớ vật lý.
• Địa chỉ trong các không gian khác nhau là độc lập.

Biến

• Biến là tên của một vùng bộ nhớ cụ thể.
• Biến lưu trữ nội dung có thể đọc/ghi.
• Kiểu dữ liệu xác định cách đọc giá trị của biến (số ô nhớ và cách tính giá trị).
• Biến địa phương được khai báo trong một khối lệnh và có phạm vi hiệu lực tương ứng.

Stack Frame

• Biến trong vùng bộ nhớ của lời gọi hàm được gọi là stack frame.
• Khi hàm được gọi, bản sao của đối số được đẩy vào stack, lưu trữ địa chỉ trả về.
• Các biến địa phương được cấp phát trong stack.
• Khi hàm trả về, giá trị trả về được lưu vào thanh ghi hoặc stack.
• Frame của hàm bị đẩy ra khỏi stack, bao gồm biến địa phương, địa chỉ trả về, và tham số.

Function Call Stack

• Stack memory là khu vực bộ nhớ dùng để quản lý các lời gọi hàm.
• Mỗi lời gọi hàm tạo ra một "frame" trên stack để lưu trữ thông tin của hàm đó.

Tại Sao swap(int x, int y) Không Hoạt Động?

• Trong pass-by-value, x và y chỉ là bản sao của a và b.
• Các thay đổi trong hàm swap không ảnh hưởng đến a và b trong main().
• Khi hàm swap kết thúc, frame của nó bị loại bỏ khỏi stack.

Cơ Chế Truyền Tham Số

• Pass-by-value: Tham số là bản sao của đối số. Thay đổi tham số không ảnh hưởng đối số gốc.
• Pass-by-reference: Tham số là "nickname" của đối số. Thay đổi tham số sẽ thay đổi đối số.
• Với pass-by-value, x và y còn gọi là tham trị
• Với pass-by-reference, x và y còn gọi là tham biến
• Hằng tham số (ví dụ: const string x) không được sửa đổi trong hàm.
• Nên sử dụng const cho tất cả tham số không cần sửa đổi để tránh lỗi.
• Hằng tham biến (ví dụ: const string& y) tương đương tham trị về hiệu ứng phụ, nhưng hiệu năng tốt hơn khi làm việc với kiểu dữ liệu lớn do tránh được việc sao chép giá trị.

Biến Tham Chiếu

• Biến tham chiếu là một "nick" khác của một biến đã tồn tại.

Giá Trị Mặc Định của Tham Số

• Tham số có thể có giá trị mặc định (ví dụ: int divide(int a, int b = 2)).
• Khi gọi hàm mà không truyền giá trị cho tham số này, giá trị mặc định sẽ được sử dụng.
• Chỉ các tham số cuối cùng mới được phép có giá trị mặc định.

Hàm Đệ Quy:

• Hàm đệ quy là hàm gọi chính nó.
• Cần có trường hợp cơ bản để dừng đệ quy.

Dưới đây là cách hàm đệ quy hoạt động và ví dụ về hàm tính giai thừa:

• Trường hợp cơ bản: Khi x <= 1, hàm trả về 1.
• Trường hợp đệ quy: Khi x > 1, hàm trả về x * factorial(x-1).
• Hàm đệ quy đưa bài toán về các bài toán con nhỏ hơn, hội tụ về trường hợp cơ bản.

Ví dụ:

long factorial(long x) {
    if (x > 1)
        return (x * factorial(x-1));
    else
        return 1;
}

Tìm Kiếm Nhị Phân Đệ Quy:

• Tìm kiếm nhị phân (binary search) là một thuật toán tìm kiếm hiệu quả trên mảng đã sắp xếp.
• Thuật toán này có thể được thực hiện đệ quy.

Công thức đệ quy:

• Nếu a[mid] < key: Tìm kiếm trong nửa phải của mảng: search(mid+1, high)
• Nếu a[mid] > key: Tìm kiếm trong nửa trái của mảng: search(low, mid-1)

Các trường hợp cơ bản:

• a[mid] == key: Tìm thấy phần tử.
• low > high: Không tìm thấy phần tử.