10 ví dụ bằng C++ sử dụng đệ quy

Bài viết này chứa 10 ví dụ điển hình về sử dụng phương pháp đệ quy để giải quyết các bài toán lập trình bằng C++.

1. Tính giai thừa

Tính giai thừa của một số bằng đệ quy.

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

2. Chuỗi Fibonacci

Tính giá trị số Fibonacci thứ n bằng cách sử dụng đệ quy.

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2); // dammio.com
}

3. Tổng các số tự nhiên

Tính tổng của n số tự nhiên đầu tiên bằng đệ quy.

int sumOfNaturalNumbers(int n) {
    if (n == 1) {
        return 1;
    }
    return n + sumOfNaturalNumbers(n - 1);
}

4. Lũy thừa

Tính kết quả của x lũy thừa của y bằng cách sử dụng đệ quy.

double power(double x, int y) {
    if (y == 0) {
        return 1;
    }
    return x * power(x, y - 1);
}

5. Tìm kiếm nhị phân

Thực hiện tìm kiếm nhị phân trên một mảng được sắp xếp bằng cách sử dụng đệ quy.

int binarySearch(int arr[], int low, int high, int target) {
    if (low > high) {
        return -1; // Element not found
    }
    int mid = (low + high) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearch(arr, mid + 1, high, target);
    } else {
        return binarySearch(arr, low, mid - 1, target);
    }
}

6. Đảo ngược chuỗi

Đảo ngược chuỗi bằng đệ quy.

std::string reverseString(const std::string& str) {
    if (str.empty()) {
        return "";
    }
    return reverseString(str.substr(1)) + str[0]; // dammio.com
}

7. Tháp Hà Nội

Giải bài toán Tháp Hà Nội bằng phương pháp đệ quy.

void towerOfHanoi(int n, char source, char auxiliary, char destination) {
    if (n == 1) {
        std::cout << "Move disk 1 from " << source << " to " << destination << std::endl;
        return;
    }
    towerOfHanoi(n - 1, source, destination, auxiliary);
    std::cout << "Move disk " << n << " from " << source << " to " << destination << std::endl;
    towerOfHanoi(n - 1, auxiliary, source, destination);
}

8. GCD (Greatest Common Divisor – Ước Chung Lớn Nhất)

Tìm ước chung lớn nhất của hai số bằng thuật toán Euclide với đệ quy.

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

9. Tổng các phần tử trong mảng

Tính tổng các phần tử trong mảng bằng đệ quy.

int sumOfArray(int arr[], int size) {
    if (size == 0) {
        return 0;
    }
    return arr[size - 1] + sumOfArray(arr, size - 1); // dammio.com
}

10. Làm phẳng danh sách

Làm phẳng danh sách lồng nhau bằng cách sử dụng đệ quy.

std::vector<int> flatten(const std::vector<std::vector<int>>& nestedList) {
    std::vector<int> result;
    for (const auto& nested : nestedList) {
        if (nested.empty()) {
            continue;
        }
        if (nested.size() == 1) {
            result.push_back(nested[0]);
        } else {
            auto flattened = flatten({nested});
            result.insert(result.end(), flattened.begin(), flattened.end()); // dammio.com
        }
    }
    return result;
}

Những ví dụ này sử dụng đệ quy để giải các bài toán khác nhau trong C++, bao gồm các phép tính toán học, thuật toán tìm kiếm, thao tác chuỗi và giải quyết vấn đề. Hàm đệ quy chia các bài toán phức tạp thành các bài toán con đơn giản hơn, khép kín, khiến chúng trở thành một công cụ mạnh mẽ trong lập trình.