Rate this post

Đệ quy là một kỹ thuật lập trình mà một hàm gọi chính nó để thực hiện một tác vụ. Trong C++, đệ quy có thể được sử dụng để giải quyết các vấn đề mà có thể được chia nhỏ thành các vấn đề con có cùng kiểu và cùng giải thuật.

Các bài viết liên quan

Ví dụ về đệ quy trong C++ là giải quyết bài toán Fibonacci:

#include <iostream>
using namespace std;

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

int main()
{
    int n;
    cout << "Enter the number: ";
    cin >> n;
    cout << "Fibonacci number is: " << fibonacci(n);
    return 0;
}

Trong ví dụ trên, hàm fibonacci() được định nghĩa với một tham số n và trả về giá trị Fibonacci thứ n. Nếu n <= 1, nó trả về giá trị n. Nếu không, nó gọi đệ quy hàm fibonacci() với n-1 và n-2 và trả về tổng của hai giá trị đó.

Lưu ý rằng đệ quy cần có điều kiện dừng để tránh vòng lặp vô hạn và tài nguyên hệ thống sẽ bị tạm thời hết.

khi nào ta sử dụng hàm đệ quy

Khi nào một vấn đề có thể được chia nhỏ thành các vấn đề con có cùng kiểu và cùng giải thuật thì ta có thể sử dụng đệ quy để giải quyết.

Ví dụ như giải quyết bài toán tìm kiếm nhị phân, sắp xếp, tìm kiếm cây nhị phân, duyệt cây, tìm kiếm đồ thị, giải quyết bài toán cấp số và nhiều bài toán khác.

Cũng cần lưu ý rằng đệ quy có thể dễ dàng giải quyết vấn đề nhưng có thể sẽ tốn nhiều tài nguyên hơn so với giải thuật khác.

Khử đệ quy trong c++

Trong C++, có hai cách thường dùng để khử đệ quy: sử dụng vòng lặp và sử dụng đệ quy tuyến tính (iterative recursion).

Sử dụng vòng lặp:

#include <iostream>
using namespace std;

int fibonacci(int n)
{
    int a = 0, b = 1, c, i;
    if (n == 0)
        return a;
    for (i = 2; i <= n; i++)
    {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main()
{
    int n;
    cout << "Enter the number: ";
    cin >> n;
    cout << "Fibonacci number is: " << fibonacci(n);
    return 0;
}

Sử dụng đệ quy tuyến tính (iterative recursion):

#include <iostream>
using namespace std;

int fibonacci(int n)
{
    int a = 0, b = 1, c;
    while (n-- > 0)
    {
        c = a + b;
        a = b;
        b = c;
    }
    return a;
}

int main()
{
    int n;
    cout << "Enter the number: ";
    cin >> n;
    cout << "Fibonacci number is: " << fibonacci(n);
    return 0;
}

Sử dụng vòng lặp là một cách thông dụng để khử đệ quy, nó giúp giảm tải bản tài nguyên và tăng tốc độ chương trình. Tuy nhiên, nó có thể khó để hiểu và thiếu sự trực quan so với đệ quy.

Sử dụng đệ quy tuyến tính là một cách khác để khử đệ quy, nó cho phép sử dụng các biến vòng lặp và các cấu trúc điều khiển để thay thế cho đệ quy. Điều này giúp giảm tải bộ nhớ và tăng tốc độ chương trình nhưng vẫn giữ được sự trực quan và dễ hiểu.

Cần lưu ý rằng khi chuyển từ đệ quy sang vòng lặp hoặc đệ quy tuyến tính, cần đảm bảo rằng chương trình vẫn hoạt động đúng và có kết quả chính xác.

một số ví dụ về đệ quy c++

  1. Tìm kiếm nhị phân:
#include <iostream>
using namespace std;

int binarySearch(int arr[], int left, int right, int x)
{
    if (right >= left)
    {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, left, mid - 1, x);
        return binarySearch(arr, mid + 1, right, x);
    }
    return -1;
}

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int x = 5;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
    if (result == -1)
        cout << "Element not present";
    else
        cout << "Element found at index " << result;
    return 0;
}
  1. Sắp xếp chèn (Insertion Sort):
#include <iostream>
using namespace std;

void insertionSort(int arr[], int n)
{
    int i, key, j;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

  1. Tìm kiếm cây nhị phân (Binary Search Tree):
#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node* left;
    Node* right;
};

Node* newNode(int data)
{
    Node* node = new Node();
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Node* insert(Node* root, int data)
{
    if (root == NULL)
        return newNode(data);
    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);
    return root;
}

bool search(Node* root, int data)
{
    if (root == NULL)
        return false;
    if (root->data == data)
        return true;
    if (root->data < data)
        return search(root->right, data);
    else
        return search(root->left, data);
}

int main()
{
    Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
    int number;
    cout << "Enter a number to be searched\n";
    cin >> number;
    if (search(root, number) == true)
        cout << "Found\n";
    else
        cout << "Not Found\n";
    return 0;
}
  1. Giải quyết bài toán cấp số (Tower of Hanoi):
#include <iostream>
using namespace std;

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)
{
    if (n == 1)
    {
        cout << "Move disk 1 from rod " << from_rod << " to rod " << to_rod << endl;
        return;
    }
    towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
    cout << "Move disk " << n << " from rod " << from_rod << " to rod " << to_rod << endl;
    towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

int main()
{
    int n;
    cout << "Enter the number of disks: ";
    cin >> n;
    towerOfHanoi(n, 'A', 'C', 'B');
    return 0;
}

Đệ quy là một kỹ thuật lập trình rất mạnh mẽ và linh hoạt, nó cho phép chúng ta giải quyết các vấn đề phức tạp mà có thể được chia nhỏ thành các vấn đề con có cùng kiểu và cùng giải thuật. Tuy nhiên, cần lưu ý rằng đệ quy có thể tốn nhiều tài nguyên hơn so với giải thuật khác, vì vậy cần cân nhắc khi sử dụng đệ quy trong chương trình.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Contact Me on Zalo
Call now