Kết nối

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

187 lượt xem 
 
Thể loại: C++, Ngôn ngữ lập trình 

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.

Liên quan:  So sánh C# và Python, nên lựa chọn ngôn ngữ nào?
Trích dẫn bài viết
  • APA:
    Dammio. (2023). 10 ví dụ bằng C++ sử dụng đệ quy. https://www.dammio.com/2023/10/08/10-vi-du-bang-c-su-dung-de-quy.
  • BibTeX:
    @misc{dammio,
    author = {Dammio},
    title = {10 ví dụ bằng C++ sử dụng đệ quy},
    year = {2023},
    url = {https://www.dammio.com/2023/10/08/10-vi-du-bang-c-su-dung-de-quy},
    urldate = {2024-04-24}
    }
Theo dõi
Thông báo của
guest
1 Bình luận
Cũ nhất
Mới nhất Được bỏ phiếu nhiều nhất
Phản hồi nội tuyến
Xem tất cả bình luận
trackback

[…] Trong ví dụ trên, tính giai thừa của 1 số n sẽ đệ quy thành tính giai thừa của tích n * factorial(n – 1) và để tính factorial(n – 1) thì chúng ta phải tính (n-1) * factorial(n – 2) và tiếp tục cho đến khi n=1. Do đó lúc này tính n sẽ trở thành tính dãy n * (n – 1)*(n – 2)*…*1. Với các bài toán khác, bạn có thể tham khảo 10 ví dụ bằng C++ sử dụng đệ quy. […]

1
0
Rất thích suy nghĩ của bạn, hãy bình luận.x