C++ Recursion

C++ Recursion: Định nghĩa và Cú pháp

Đệ quy (Recursion) là một kỹ thuật lập trình trong đó một hàm gọi chính nó để giải quyết một vấn đề. Kỹ thuật này thường được sử dụng để giải quyết các bài toán có thể được chia nhỏ thành các bài toán con giống hệt nhau. Đệ quy thường hữu ích trong việc xử lý các cấu trúc dữ liệu như cây hoặc đồ thị, và trong việc giải quyết các bài toán mà cách tiếp cận lặp lại (iterative) có thể trở nên phức tạp.

Cú pháp của hàm đệ quy trong C++

Cú pháp của một hàm đệ quy trong C++ tương tự như một hàm thông thường. Tuy nhiên, một hàm đệ quy sẽ bao gồm tối thiểu hai thành phần chính: điều kiện dừng (base case) và việc gọi hàm đệ quy. Điều kiện dừng là điều kiện giúp hàm biết khi nào thì không cần gọi chính nó nữa.

return_type function_name(parameters) {
    // Điều kiện dừng
    if (condition) {
        return base_case_value;
    }
    // Gọi hàm đệ quy
    return function_name(modified_parameters);
}

Ví dụ về Đệ quy trong C++

1. Tính giai thừa

Giai thừa của một số nguyên dương n (ký hiệu là n!) được định nghĩa là sản phẩm của tất cả các số nguyên dương từ 1 đến n. Đệ quy có thể được sử dụng để tính giai thừa như sau:

#include <iostream>
using namespace std;

int factorial(int n) {
    // Điều kiện dừng
    if (n == 0 || n == 1) {
        return 1;
    }
    // Gọi hàm đệ quy
    return n * factorial(n - 1);
}

int main() {
    int number = 5;
    cout << "Giai thua cua " << number << " la: " << factorial(number) << endl;
    return 0;
}

2. Tính Fibonacci

Chuỗi Fibonacci là một chuỗi số trong đó mỗi số là tổng của hai số trước đó. Chuỗi này bắt đầu với hai số 0 và 1. Đệ quy có thể được sử dụng để tìm số Fibonacci tại vị trí n như sau:

#include <iostream>
using namespace std;

int fibonacci(int n) {
    // Điều kiện dừng
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    // Gọi hàm đệ quy
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int position = 5;
    cout << "So Fibonacci tai vi tri " << position << " la: " << fibonacci(position) << endl;
    return 0;
}

Kết luận

Đệ quy là một công cụ mạnh mẽ trong lập trình C++. Mặc dù kỹ thuật này có thể dẫn đến việc tiêu tốn nhiều bộ nhớ và thời gian tính toán (đặc biệt trong các ví dụ như cây Fibonacci), nhưng nếu được sử dụng đúng cách, đệ quy có thể giúp mã nguồn trở nên ngắn gọn và dễ hiểu hơn. Khi học về đệ quy, hãy chú ý đến cách xác định điều kiện dừng để tránh việc gọi vô hạn và gây ra tràn ngăn xếp.