Hôm nay mình sẽ áp dụng thuật toán đệ quy vào một ứng dụng thực tế dùng trong đời sống hàng ngày: comment nhiều cấp độ.

1. Tạo bảng cơ sở dữ liệu

CREATE TABLE "comment" (
    id text NOT NULL,
    "content" text NOT NULL,
    created_at timestamp NULL DEFAULT now(),
    user_name text NOT NULL,
    parent_id text,
    CONSTRAINT comment_pkey PRIMARY KEY (id)
);

insert into comment values ('123','Comment cấp 1 - phần tử 1', now(), 'Đức', null)
insert into comment values ('456','Comment cấp 1 - phần tử 2', now(), 'Hà', null)
insert into comment values ('abc','Comment cấp 2 - phần tử 1', now(), 'Tuấn Anh', '123')
insert into comment values ('def','Comment cấp 2 - phần tử 2', now(), 'Hiên', '123')
insert into comment values ('DEF','Comment cấp 3 - phần tử 1', now(), 'Hà', 'abc')
insert into comment values ('GHI','Comment cấp 3 - phần tử 2', now(), 'Đức', 'abc')

2. Truy vấn nhiều cấp bằng PostgreSql

Thử gõ lệnh sau:

SELECT * FROM comment

Ta thu được kết quả:

comments

Giờ ta thử lấy comment với id là 123 và các comment cấp con của nó sử dụng recursive query do PostgreSQL hỗ trợ:

WITH RECURSIVE recursion AS (
    select * from comment
    where id = '123'
    UNION
        select cmt2.* from comment cmt2
        INNER JOIN recursion r ON r.id = cmt2.parent_id
)
select * from recursion

Ta thu được kết quả:

recursive-result

3. Mapping vào trong struct golang

Cách làm trên ta chỉ có thể lấy ra danh sách các comment (cả cấp con và cha) trải ra thành các row. Khi render ra file json, nó sẽ chỉ là một mảng các comment object như sau:

[
    {
        "id":"123",
        "content":"Comment cấp 1 - phần tử 1",
        "parent_id":""
    },
    {
        "id": "abc",
        "content": "Comment cấp 2 - phần tử 1",
        "parent_id":"123"
    },
    ........
]

Như vậy khi mapping vào struct golang sẽ chỉ ra một mảng slice các comment, không thể xác định đâu là cấp con, đâu là cấp cha (ngay cả khi có thể xử lý logic sẽ cực kỳ rắc rối phức tạp).

Để dễ dàng phân biệt comment cấp trong và cấp ngoài, đầu tiên ta định nghĩa model như sau:

/* Mỗi comment có thể chứa list danh sách các comment con của nó, trong
mỗi comment con lại chứa list các comment con bên trong nữa và cứ như thế
*/
type Comment struct{
    Id          string    `json:"id"`
    Content     string    `json:"content"`
    UserName    string    `json:"user_name"`
    CreatedAt   string `json:"created_at"`
    SubComments []Comment `pg:",array" json:"sub_comments"` //Để lấy được vô vàn comment cấp trong, ta khai báo subcomments là slice của object Comment gọi lại chính nó
}

Để mapping ra struct Comment trên, ta cần query ra các cột với tên và kiểu dữ liệu tương ứng, trong đó sub_comments để mapping được cần trả ra kiểu jsonb[] (mảng json) trong postgres. Để làm được điều này cần khai báo chính function đệ quy ngay trong cơ sở dữ liệu và gọi function đó trong câu query.

Khai báo function

create or replace function subcomments (parent_ids text)
returns jsonb[] as $$
begin
    return (
        select array_agg(row_to_json(d)) from
            (
            select id, content, created_at, user_name, subcomments(id) AS sub_comments
            from comment
            where parent_id = parent_ids
            ) d
        );
end;
$$ LANGUAGE plpgsql

Giờ là lúc code gọi vào database và truy vấn ra dữ liệu. Toàn bộ đoạn code như sau:

package main

import (
    "fmt"
    "github.com/go-pg/pg/v10"
    "github.com/kataras/iris/v12"
)

type Comment struct {
    Id          string    `json:"id"`
    Content     string    `json:"content"`
    UserName    string    `json:"user_name"`
    CreatedAt   string `json:"created_at"`
    SubComments []Comment `pg:",array" json:"sub_comments"`
}

func main() {
    //Kết nối đến CSDL, ở đây là địa chỉ sử dụng ở trên máy của mình
    var db = pg.Connect(&pg.Options{
        User:     "postgres",
        Password: "123456",
        Database: "postgres",
        Addr:     "localhost:5432",
    })
    defer db.Close()
    //Bắt đầu sử dụng iris framework
    app := iris.New()

    //Định nghĩa router /comment, khi gọi vào sẽ xử lý logic bên trong
    app.Get("/comment", func(ctx iris.Context) {
        var comments []Comment

        //Query lấy ra toàn comment, trong đó có gọi đến hàm subcomments ta định nghĩa ở trên
        _, err := db.Query(&comments, `
        select id, content, created_at, user_name, subcomments(id) AS sub_comments
        from comment where parent_id is null
        `)
        if err != nil {
            fmt.Println(err)
            return
        }
        //Nếu thành công trả ra list comment dạng JSON
        _, _ = ctx.JSON(comments)
    })

    //Lắng nghe ở cổng 8080 của máy local
    _ = app.Listen(":8080")
}

Cuối cùng chạy project và dùng Postman gọi API http://localhost:8080/comment và thu được kết quả:

[
    {
        "id": "123",
        "content": "Comment cấp 1 - phần tử 1",
        "user_name": "Đức",
        "created_at": "2021-11-04 20:54:19.223643",
        "sub_comments": [
            {
                "id": "abc",
                "content": "Comment cấp 2 - phần tử 1",
                "user_name": "Tuấn Anh",
                "created_at": "2021-11-04T20:54:24.037911",
                "sub_comments": [
                    {
                        "id": "DEF",
                        "content": "Comment cấp 3 - phần tử 1",
                        "user_name": "Hà",
                        "created_at": "2021-11-04T20:54:29.192329",
                        "sub_comments": null
                    },
                    {
                        "id": "GHI",
                        "content": "Comment cấp 3 - phần tử 2",
                        "user_name": "Đức",
                        "created_at": "2021-11-04T20:54:31.575165",
                        "sub_comments": null
                    }
                ]
            },
            {
                "id": "def",
                "content": "Comment cấp 2 - phần tử 2",
                "user_name": "Hiên",
                "created_at": "2021-11-04T20:54:26.452044",
                "sub_comments": null
            }
        ]
    },
    {
        "id": "456",
        "content": "Comment cấp 1 - phần tử 2",
        "user_name": "Hà",
        "created_at": "2021-11-04 20:54:21.79084",
        "sub_comments": null
    }
]

4. Lấy data từ backend trả về và render ra giao diện:

Giả sử khi gọi API và lấy được dữ liệu như trên, làm sao dùng javascript (hay jquery) để gắn dữ liệu đó vào trong thẻ HTML?

Nếu dùng thuật toán duyệt mảng không thôi sẽ là điều bất khả thi, do ta không thể biết có bao nhiêu cấp độ comment sẽ được trả ra. Lúc này phương pháp đệ quy mới phát huy tối đa tác dụng của nó.

index.html

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <!--Ta sẽ gắn danh sách comment vào trong này-->
    <div id="comments">
        Comments
    </div>
</body>
<script src="https://code.jquery.com/jquery-3.6.0.min.js" integrity="sha256-/xUj+3OJU5yExlq6GSYGSHk7tPXikynS7ogEvDej/m4=" crossorigin="anonymous"></script>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/3.5.1/jquery.min.js"></script>

<script>
//Ở đây ta sẽ mockup dữ liệu comment để thử nghiệm render ra giao diện thay vì gọi API
    var comments = [
    {
        id: "123",
        user_name: "Đức",
        content: "Comment cấp 1 - phần tử 1",
        sub_comments: [
        {
            id: "abc",
            user_name: "Tuấn Anh",
            content: "Comment cấp 2 - phần tử 1",
            sub_comments: [
            {
                id: "DEF",
                user_name: "Đức",
                content: "Comment cấp 3 - phần tử 1",
                sub_comments: null
            },
            {
                id: "GHI",
                user_name: "Đức",
                content: "Comment cấp 3 - phần tử 2",
                sub_comments: null
            }
            ]
        },
        {
            id: "def",
            user_name: "Hiên",
            content: "Comment cấp 2 - phần tử 2",
            sub_comments: null
        }
        ]
    }, {
        id: "456",
        user_name: "Hà",
        content: "Comment cấp 1 - phần tử 2",
        sub_comments: null
    }]

    /*
    Khai báo function đệ quy:
    - parameter id là id của thẻ html cần gắn comment vào (thường được đặt theo id của comment)
    - cmts là mảng các comment object
    */
    function AppendComments(id, cmts) {
        //Xác định điểm dừng khi cmts null
        if (cmts == null) {
            return
        }

        for (let i = 0; i < cmts.length; i++) {
            let text = `
            <li id="${cmts[i].id}">
                <strong>UserName</strong>: ${cmts[i].user_name}<br>
                <strong>Content</strong>: ${cmts[i].content} <br>
                <strong>Reply</strong>:
            </li>
            `
            //Append từng object comment vào thẻ id
            $(id).append(`<ul>${text}</ul>`)

            /*Trong một object comment có thể chứa các subcomments, ta sử dụng hàm đệ quy
            để thực hiện lại tác vụ append như trên. */
            AppendComments(`#${cmts[i].id}`, cmts[i].sub_comments)
        }
    }

    //Gọi function đệ quy truyền tham số tương ứng
    AppendComments('#comments', comments)
</script>
</html>

Kết quả:

comment_interface

Kết luận

Như vậy bạn có thể thấy với một bài tập trả ra comment nhiều cấp độ, mà thuật toán đệ quy phải sử dụng ở mọi nơi, từ cơ sở dữ liệu cho đến code javascript chọc vào DOM căn bản. Hy vọng giờ bạn đã thấy ứng dụng của thuật toán đệ quy trong thực tế đời sống (như facebook có chức năng comment nhiều cấp) - thứ bạn không thể thấy khi học trên lớp.