Thuật toán đệ quy trong C++

4
Lập trình C++

Thuật toán đệ quy là một phương pháp giải quyết vấn đề bằng cách chia nhỏ nó thành các bài toán con cùng loại nhỏ hơn. Thuật toán đệ quy được thể hiện bằng cách sử dụng một hàm để gọi đến chính nó với các giá trị đầu vào khác nhau để giải quyết các bài toán con.

Có thể tóm tắt các bước để thực hiện thuật toán đệ quy như sau:

  1. Xác định điều kiện dừng: điều kiện nào khiến cho thuật toán không thể chạy tiếp nữa (ví dụ: kích thước của bài toán con bằng 0 hoặc 1).
  2. Chia nhỏ bài toán thành các bài toán con cùng loại nhỏ hơn: sử dụng đệ quy để giải quyết các bài toán con này.
  3. Kết hợp kết quả từ các bài toán con để giải quyết bài toán lớn hơn.

Ví dụ, một thuật toán đệ quy để tính giai thừa của một số nguyên dương có thể được thể hiện như sau:

#include <iostream>
using namespace std;

int giaiThua(int n) {
    if (n == 0) {
        return 1;
    }
    else {
        return n * giaiThua(n - 1);
    }
}

int main() {
    int n;
    cout << "Nhap so nguyen duong n: ";
    cin >> n;
    cout << "Giai thua cua " << n << " la: " << giaiThua(n) << endl;
    return 0;
}

Trong đó, hàm giaiThua là một hàm đệ quy được sử dụng để tính giai thừa của một số nguyên dương n. Nếu n bằng 0, hàm trả về 1 (điều kiện dừng), còn nếu n khác 0, hàm sẽ gọi đến chính nó với đầu vào là n-1 (bài toán con nhỏ hơn), và kết hợp kết quả của các bài toán con để tính ra giá trị giai thừa của n. Hàm main sử dụng hàm giaiThua để tính giai thừa của một số nguyên dương n được nhập từ bàn phím..,

BÀI VIẾT LIÊN QUANXEM THÊM