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/

Tìm kiếm nhị phân | Binary search

Chào mừng các bạn đã đến với thachleblog, bài viết hôm nay mình sẽ trình bày về một thuật toán tìm kiếm đơn giản nhưng lại cực kỳ hiệu quả, được ứng dụng rất nhiều trong thực tế đó là tìm kiếm nhị phân hay còn gọi là binary search. Nào, chúng ta cùng bắt đầu nhé.

Giới thiệu

Nói về bài toán tìm kiếm, chúng ta gặp rất nhiều trong thực tế đó là khi chúng ta tìm tên mình danh sách đăng ký vận động viên marathon, tìm tên mình trong danh sách nhân viên xuất sắc của năm được dán ở đâu đó. Thời đại này cần tìm kiếm thì nhấn nút thôi chứ lấy ví dụ về tìm kiếm bằng mắt khó quá, hehe.

Cách đơn giản nhất là chúng ta sẽ dò tuần tự (đối với các danh sách ngắn), cho đến khi tìm đúng đến tên mình. Hoặc cũng có cách nhanh hơn là vì các danh sách thường sắp xếp theo tên, do đó, mình chỉ việc dò tên mình trong phạm vi bản chữ cái tên mình. Ví dụ, tên mình bắt đầu bằng chữ cái T, do đó mình chỉ việc tìm tên trong phạm vi chữ T. Tùy vào vị trí mình chọn mà mình sẽ dò tên mình theo hướng tiến hoặc lùi.

Trong lập trình, để tìm kiếm một phần tử trong mảng, danh sách. Cách tìm kiếm đơn giản nhất là tìm kiếm tuần tự, hay còn gọi là tìm kiếm lân cận (linear search). Ý tưởng rất đơn giản, ta chỉ việc kiểm tra lần lượt các phần tử từ đầu đến cuối để tìm phần tử thỏa điều kiện.

Ví dụ: Cho mảng gồm 16 số nguyên tố tăng dần: 2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 31, 37, 39 ,41, 43, 47

Để tìm vị trí số 13 trong mảng, ta cứ việc kiểm tra lần lượt phần tử đầu tiên là 2, cho đến hết mảng và trả về vị trí của số 13.

Trường hợp tổng quát, nếu may mắn, số ở vị trí đầu tiên là số cần tìm thì ta chỉ cần 1 lần kiểm tra. Tuy nhiên, nếu số cần tìm ở vị trí cuối cùng hoặc không có trong mảng, ta sẽ phải thực hiện kiểm tra đến 16 lần.

Vì là mảng các số nguyên tăng dần nên trong trường hợp này ta có thể dùng thuật toán tìm nhị phân . Cách thực hiện rất đơn giản, đầu tiên ta kiểm tra số chính giữa mảng có phải là số cần tìm hay không, nếu không ta có thể loại bỏ 1/2 số phần tử và tiếp tục tìm kiếm trong 1/2 còn lại. Cứ mỗi lần chọn phần tử để so sánh, ta sẽ loại bỏ được 1/2 số phần tử không phù hợp. Ở ví dụ trên, việc tìm kiếm nhị phân sẽ được thực hiện như sau:

– Đầu tiên chọn phần tử để kiểm tra ở giữa mảng là 19, vì số cần tìm là 13 nhỏ hơn 19 nên ta loại bỏ được 1/2 phần tử từ 19 – 47 và chỉ cần tìm trong phạm vi từ 2 – 17.

– Lần tiếp theo tương tự ta chọn số 7, vì 7 nhỏ hơn 13 nên ta cũng loại bỏ được 1/2 số phần tử và tiếp tục tìm trong phạm vi từ 11 – 17.

– Lần cuối cùng ta chọn 13 để so sánh, lần này ta trả về kết quả cần tìm.

Trong cách tìm kiếm nhị phân, rõ ràng, số lần chúng ta kiểm tra sẽ ít hơn rất nhiều so với tìm kiếm tuần tự, trong trường hợp trên, trường hợp xấu nhất ta cũng mất tối đa là 5 lần để kiểm tra.

Đặc biệt, vì mỗi lần chọn số cần tìm là lại loại bỏ được 1/2 phần tử, nên khi số lượng phần tử cần tìm tăng lên gấp đôi, ta chỉ mất thêm 1 lần để kiểm tra. Số lần cần kiếm tra trong thuật toán tìm kiếm nhị phân sẽ là logarit cơ số 2 của n. Để xem mức độ hiệu quả của thuật toán tìm kiếm nhị phân, ta có thể xem bảng logn:

Thử tưởng tượng, nếu bạn cần tìm user theo id, trong danh sách (list) user được sắp xếp id tăng dần lên đến xấp xỉ 1000 phần tử, chúng ta chỉ mất tối đa 11 lần so sánh để tìm ra kết quả. Một sự cải thiện đáng kinh ngạc so với 1000 lần kiếm tra (trường hợp xấu nhất) theo thuật toán tìm kiếm tuần tự!

Giải thuật

Giải thuật của tìm kiếm nhị phân rất đơn giản, như phần ví dụ ở trên, mình chỉ cần thực hiện bằng các bước.

1. Chọn min là 0 và max = n -1 (n là số phần tử của mảng)

2. Nếu max nhỏ hơn min, số cần tìm không tồn tại, trả về -1

3. Chọn mid là số chính giữa mảng

4. Nếu mid là số cần tìm (target), ta trả về giá trị cần tìm

5.  Nếu mid < target, ta set lại min = mid + 1

6. Nếu mid > target, ta set lại max = mid – 1;

7. Lập tại bước 2

Code

Có nhiều cách để implement tìm kiếm nhị phân, nhưng thường thì mình dùng vòng lặp while

package binarysearch;
 
/**
 *
 * @author thachlp
 */
public class BinarySearch {
 
    private static int binarySearch(int arr[], int target) {
        int min = 0;
        int max = arr.length - 1;
        int mid = 0;
 
        while (min <= max) {
            mid = (min + max) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
 
        return -1;
    }
 
    public static void main(String[] args) {
        int[] arr = {2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 31, 37, 39 ,41, 43, 47};
        System.out.println("Found 13 at index: " + binarySearch(arr, 13));
    }
 
}

Đoạn code trên là ví dụ minh họa với các phần tử là số nguyên, nhưng chúng ta cũng có thể vận dụng cho các trường hợp các giá trị của phần tử là chữ cái, số… miễn là chúng được sắp xếp tăng dần. (Chúng ta cũng có thể tối ưu danh sách trước khi tìm kiếm bằng cách sort object, xem thêm tại đây)

Kết

Qua bài viết của mình, hy vọng các bạn đã cảm thấy được sự hiệu quả của thuật toán tìm kiếm nhị phân, qua đó có thể tự tin vận dụng vào dự án của mình đạt hiệu quả cao nhất. Các bài sau, mình sẽ tiếp tục giới thiệu đến các giải thuật khác. Cảm ơn các bạn đã đọc và hẹn gặp lại.