Thuật toán đệ quy – Recursion algorithms

Chào mừng các bạn đã quay trở lại với thachleblog, ở bài trước mình đã giới thiệu với các bạn về thuật toán tìm kiếm nhị phân, hy vọng các bạn đã hiểu rõ và có thể tự tin áp dụng cho dự án của mình. Ở bài này, mình sẽ tiếp tục giới thiệu một thuật toán cơ bản khác đó chính là đệ quy. Lý do mình viết bài viết này là bởi vì thuật toán đệ quy rất căn bản, là tiền đề cho các thuật toán sau này như quick sort, merge sort, tree, graph… Mục tiêu bài viết này của mình là các bạn hiểu, nhận dạng và hiểu được ưu nhược điểm của thuật toán đệ quy. Nào, chúng ta cùng bắt đầu nhé.

Giới thiệu

Trước khi mình đi vào định nghĩa khá là ngắn gọn về khái niệm “đệ quy là gì” thì mình xin chia sẻ về một món đồ chơi mà mình thấy khá là thú vị.

Con búp bê bằng gỗ này được bán rất nhiều ở các khu hội chợ, các khu du lịch. Cấu tạo của nó rất đặc biệt, bên trong thân rỗng, chứa một con búp bê khác tương tự nhưng kích thước nhỏ hơn, và con tiếp theo cũng thế, cứ như vậy cho đến con nhỏ nhất (các bạn có thể mua về để rảnh rảnh vặn ra xếp như hình trên rồi lại xếp vào, cho bớt rảnh rỗi, hehe).

Tại sao mình lại nhắc đến cái con búp bê này, bởi vì cấu tạo của nó rất giống với thuật toán đệ quy. Bên trong con búp bê này chứa một con búp bê khác tương tự nó nhưng với kích thước nhỏ hơn và bên trong con nhỏ hơn đó cũng chứa một con nhỏ hơn khác, cho đến con nhỏ nhất (không chứa được thêm con nào). Bản thân thuật toán đệ quy chính là gọi lại chính nó với input nhỏ hơn (subproblem), cho đến điểm dừng (base case).

Ví dụ: tính giai thừa của số tự nhiên n

Thông thường, cách đơn giản nhất là dùng vòng lặp, chẳng cần quan tâm đệ quy là cái khỉ gì:

static int factorial(int n) {
        int result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }

Tuy nhiên, chúng ta cũng có thể tính n giai thừa bằng đệ quy như sau:

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

Để hiểu đệ quy chạy như thế nào thì các bạn hãy hình dung lại cấu trúc của con búp bê. Với đệ quy, bên trong method facotorial(n) sẽ gọi method factorial(n-1) và cứ thế đến factorial(0):

  • factorial(n) = n * factorial(n-1)

  • factorial(n-1)= n-1 * factorial(n-2)

  • ….

  • factorial(0) = 1;

Cấu trúc

Nhìn vào ví dụ trên chúng ta có thể thấy đệ quy thường gồm 2 phần:

  • Base case: điểm mà vấn đề đã được chia đến mức nhỏ nhất và đã có thể dừng lại (factorial(0))

  • Recursion case: phần gọi lại chính nó với input nhỏ hơn. Cho đến khi gặp base case

So sánh với vòng lặp

Từ ví dụ trên, ta có thể nhận thấy thuật toán đệ quy sẽ tốn nhiều bộ nhớ hơn so với dùng vòng lặp, vì method được gọi lại nhiều lần, mỗi lần gọi method sẽ được lưu vào vùng nhớ stack cho đến basecase. Do đó, theo mình, trong các trường hợp thông thường, nếu có thể dùng vòng lặp thì hãy dùng vòng lặp, chẳng nên “làm màu” làm gì, hehe.

Tuy nhiên, thuật toán đệ quy lại cực kỳ hiệu quả và tường minh trong các bài toán duyệt trees, grapth… mà có thể mình sẽ giới thiệu ở các phần sau.

Tìm kiếm nhị phân bằng đệ quy

Mỗi bài toán được viết bằng đệ quy thì có thể chuyển sang dùng vòng lặp và ngược lại. Ở bài trước, mình đã viết thuật toán tìm kiếm nhị phân (binary search) bằng vòng lặp while, hôm nay mình sẽ tiếp cận bằng thuật toán đệ quy.

Giải thuật rất đơn giản, sau khi chọn điểm chính giữa mảng và so sánh với giá trị cần tìm, ta sẽ chia mảng thành 2 phần. Sau khi xác định giá trị cần tìm ở phần nào ta lại tiếp chọn lại điểm chính giữa của mảng con đó và và so sánh … Rõ ràng cách tiếp cận này cho ta cái nhìn rõ ràng hơn về khái niệm “nhị phân” tức là chia làm đôi.

int binarySearch(int arr[], int l, int r, int x) {
        if (r >= l) {
            int mid = l + (r - l) / 2;
 
            // If the element is present at the 
            // middle itself
            if (arr[mid] == x) {
                return mid;
            }
 
            // If element is smaller than mid, then 
            // it can only be present in left subarray
            if (arr[mid] > x) {
                return binarySearch(arr, l, mid - 1, x);
            }
 
            // Else the element can only be present
            // in right subarray
            return binarySearch(arr, mid + 1, r, x);
        }
 
        // We reach here when element is not present
        //  in array
        return -1;
 
    }

(nguồn source code geeksforgeeks)

Kết

Tạm kết ở đây, thực ra kiến thức này đã được học từ năm 1, năm 2 đại học, tiếc là hồi đó mình ngơ ngơ chả biết gì, chỉ học qua loa, hậu quả là ra trường thỉnh thoảng đọc code chả biết nó là cái gì -.-. Hy vọng qua bài viết này giúp các bạn đã từng mất gốc như mình hiểu được đệ quy và qua đó hiểu được cơ chế của các thuật toán sử dụng đệ quy như quick sort, merge sort hoặc các cấu trúc duyệt trees, grapth…. Mình rất mong nhận được góp ý của các bạn để hoàn thiện bài viết hơn về cách trình bày, nội dung… Cảm ơn và hẹn gặp lại các bạn ở các bài viết sau

Link tham khảo thêm:

https://www.khanacademy.org/computing/computer-science/algorithms/recursive-algorithms/a/recursion

https://www.geeksforgeeks.org/binary-search/