Thứ năm, Tháng mười một 21
Subscribe
Đọc báo Chuyển đổi số

Đệ Quy là gì?

DTSIBy
Đệ quy là một khái niệm rất quan trọng trong cấu trúc dữ liệu và giải thuật nói riêng, và trong ngành khoa học máy tính nói chung.
Có một ví dụ rất trực quan về đệ quy là khi bạn đang đứng giữa 2 chiếc gương đối diện nhau. Khi đó, bạn sẽ thấy hình ảnh của mình được phản chiếu lại nhiều lần, mỗi lần phản chiếu lại nhỏ đi một chút, đi vào độ sâu trong gương như thể không có một điểm dừng nào.
Trong ví dụ này, “hàm đệ quy” chính là quá trình phản chiếu hình ảnh của 2 chiếc gương, với mỗi lần đệ quy thực hiện là một lần hình ảnh của bạn được phản chiếu. Quá trình đệ quy này kết thúc khi hình ảnh của bạn quá nhỏ và không thể thấy bằng mắt thường nữa. Điều này giúp mô tả sự kết thúc của đệ quy một cách rõ nét, khi nó đạt đến một điểm mà nó không còn gọi lại đệ quy nữa.
Đệ quy là một khái niệm rất quan trọng trong cấu trúc dữ liệu và giải thuật nói riêng, và trong ngành khoa học máy tính nói chung. Chúng ta cùng tìm hiểu về đệ quy trong bài viết này nhé.

1. Đệ quy là gì?

1.1. Giới thiệu khái niệm Đệ quy

Trong khoa học máy tính, khái niệm đệ quy là một phương pháp giải toán, trong đó, lời giải của bài toán phụ thuộc vào một trường hợp nhỏ hơn của cùng một bài toán đó.
Nói theo cách dễ hiểu hơn, đệ quy là một hàm mà hàm đó tự gọi chính nó. “In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.”

1.2. Một số ứng dụng cơ bản của Đệ quy

Đệ quy được ứng dụng rất rộng rãi trong ngành khoa học máy tính. Một số ứng dụng có thể kể đến gồm:
  • Thuật toán Tìm kiếm và Sắp xếp: đệ quy được sử dụng rất nhiều trong các bài toán tìm kiếm, sắp xếp. Trong quá trình tìm kiếm và sắp xếp, việc chia bài toán trở thành nhiều bài toán nhỏ hơn giúp tổng thể bài toán trở nên đễ dàng. Một số thuật toán cụ thể bao gồm: tìm kiếm nhị phân (Binary Search), sắp xếp nhanh (Quick Sort), sắp xếp trộn (Merge Sort).
  • Thuật toán trên cây (tree) và đồ thì (graph): Vì tính chất của tree và graph là các node được liên kết với nhau, việc sử dụng đệ quy để giải quyết các bài toán trên cấu trúc dữ liệu này là vô cùng hợp lý. Một số bài toán cụ thể gồm: tìm kiếm đường đi ngắn nhất, duyệt cây theo chiều sâu (BFS, DFS)
  • Quy hoạch động: Nhiều bài toán có thể sử dụng đệ quy để làm giảm độ phức tạp của thuật toán. Bài toán quy hoạch động thường được sử dụng cùng với kỹ thuật ghi nhớ để cải thiện hiệu suốt.
Nói chung, các bài toán của đệ quy giúp giải quyết các bài toán phức tạp trở nên dễ dàng hơn bằng cách chia nhỏ thành tập hợp nhiều bài toán con.

2. Cấu tạo cơ bản của Đệ quy

Cấu tạo cơ bản của đệ quy gồm 2 phần, trường hợp cơ bản (base case) và trường hợp đệ quy (recursive case).

2.1. Trường hợp cơ bản của Đệ quy – Base case

Trường hợp cơ bản (base case) của đệ quy là thành phần nhỏ nhất trong đệ quy, là trường hợp mà bài toán đã được giải quyết mà không cần phải gọi lại chính nó. Bản chất cái tên “base” cũng đã ám chỉ việc nó là nền móng quan trọng nhất trong đệ quy, nơi mà các bài toán khác cần phải sử dụng đến.
Mục tiêu của base case là tìm một điểm dừng cho đệ quy, vì nếu không có điểm dừng này, đệ quy sẽ bị chạy đến vô hạn số lần.

2.2. Trường hợp đệ quy – Recursive case

Trường hợp đệ quy (recursive case) của đệ quy là thành phần phức tạp hơn base case, do đó, nó cần thực hiện liên tiếp các hành động gọi lại để tìm ra lời giải, cho đến khi gọi đến base case.
Việc recursive case gọi liên tiếp gọi lại chính nó nhằm tiến gần đến base case, đồng thời giải quyết một bài toán nhỏ hơn so với bài toán ban đầu, cho đến khi gọi đến base case.
Mục tiêu của recursive case là cố gắng tìm ra một bài toán nhẹ nhàng, dễ giải quyết hơn cho đến khi đạt đến điểm dừng là base case.

3. Nguyên tắc chung khi xây dựng Đệ quy

Từ các thành phần cơ bản trên, chúng ta có một số nguyên tắc để xây dựng đệ quy như sau:

3.1. Xác định Base case

Base case là điều kiện mà hàm không cần gọi lại chính nó, vì thế, nó cần được xác định cực kỳ cụ thể và rõ ràng. Xác định rõ ràng base case cần trả về giá trị nào giúp cho việc xác định bài toán trở nên rõ ràng hơn.
Do mục tiêu của base case là cung cấp một giá trị cụ thể để đệ quy có điều kiện thoát, do đó base case thông thường luôn trả ra một kết quả khi có cùng một đầu ra.
Ngoài ra, base case không tạo ra hoặc thay đổi các biến, tham số bên ngoài hàm và thậm trí không thực hiện các hành động lấy dữ liệu ngay cả trong phạm vi của nó.
Từ những đặc tính trên, base case có thể coi là một pure function, do nó thoả mãn các đặc tính của pure function là luôn tạo ra một giá trị output khi input giống nhau và không tạo ra một side effect bên ngoài phạm vị của nó.

3.2. Xác định Recursion case

Recursion case là tìm và giải quyết các bài toán nhỏ hơn.
Các lần sử dụng recursion case cần đưa bài toán tiến dần tới base case. Điều này có nghĩa là, sau mỗi lần thực hiện gọi lại hàm, bài toán ban đầu cần phải trở nên dễ dàng tính toán hơn so với đầu vào ban đầu.
Nói chung, chúng ta cần xác định các vấn đề cần được chia nhỏ hơn. Tiếp theo, chúng ta sử dụng đệ quy để thực hiện giải quyết các vấn đề nhỏ hơn đó, bằng cách tìm các bài toán nhỏ hơn nữa. Bài toán sẽ kết thúc khi chúng ta chia nhỏ đến base case.
Đặc tính của recursion case thường phải sử dụng các tham số bên ngoài hoặc ít nhất là đọc dữ liệu từ bên ngoài, nên recursion case không phải là pure function.
Ngoài ra, một số bài toán có thể cho ra kết quả khác nhau khi có cùng một kết quả đầu vào (bài toán tìm đường đi ngắn nhất đôi khi có nhiều hơn một kết quả), do đó, về tổng thế thì bài toán đệ quy không phải là pure function.

4. Một số loại Đệ quy cơ bản thường gặp

4.1. Đệ quy tuyến tính – Linear Recursion

4.1.1. Định nghĩa Đệ quy tuyến tính

Đệ qui tuyến tính (Linear Recursion) là một kỹ thuật lập trình nơi một hàm gọi lại chính nó một cách trực tiếp, nhưng chỉ thực hiện một lần trong mỗi lần gọi.
Điều này tạo nên một “chuỗi” của các lời gọi hàm, với mỗi lời gọi hàm mới dựa trên kết quả của lời gọi trước đó.

4.1.2. Cấu trúc Đệ quy tuyến tính

Cấu trúc của đệ quy tuyến tính là cấu trúc đơn giản nhất trong đệ quy, khi nó luôn thực hiện gọi lại chính nó cho mỗi lần thực hiện, cho đến khi tìm đến base case.
  • Base Case: Điều kiện cơ bản để kết thúc quá trình đệ quy. Nếu không có base case, hàm sẽ tiếp tục gọi chính nó vô tận.
  • Recursive Case: Phần của hàm nơi nó gọi lại chính nó, nhưng với một đối số nhỏ hơn hoặc đơn giản hơn.

4.1.3. Phân tích BigO

  • Space Complexity: Trong đệ quy tuyến tính, độ phức tạp không gian (space complexity) thường là O(n) vì có n lời gọi hàm được lưu trữ trên stack.
  • Time Complexity: Độ phức tạp thời gian (time complexity) cũng là O(n) vì mỗi lần đệ quy, độ phức tạp về tính toán sẽ giảm đi một lượng cố định.

4.2. Đệ quy nhị phân – Binary Recursion

4.2.1. Định nghĩa Đệ quy nhị phân

Đệ quy nhị phân (Binary Recursion) là kỹ thuật lập trình mà trong đó mỗi hàm gọi lại chính nó hai lần trong mỗi lần thực thi.
Điều này làm cho kiểu đệ quy tạo có thể tạo ra một cây nhị phân tương đối phức tạp, với mỗi node trong cây có thể tạo ra hai node con tương ứng.

4.2.2. Cấu trúc Đệ quy nhị phân

  • Base Case: Điều kiện cơ bản để kết thúc quá trình đệ quy, tương đối giống với đệ quy tuyến tính.
  • Recursive Case: Phần của hàm nơi nó gọi lại chính nó, nhưng không chỉ một, mà là hai lần, thường với đối số khác nhau.

4.2.3. Phân tích BigO

  • Space Complexity: Trong đệ quy nhị phân, độ phức tạp không gian (space complexity) thường là O(n), do kiểu đệ quy này lưu trữ một thông tin dưới dạng cây nhị phân
  • Time Complexity: Độ phức tạp thời gian là O(2^n), biểu diễn cho số lượng lời gọi hàm tổng cộng mà ở đây là hai lần. Xin lưu ý rằng time complexity trên là cực kỳ lớn, do đó rất hiếm trường hợp mà chúng ta sử dụng kiểu đệ quy này trong thực tế.
Ngoài ra, các kiểu đệ quy đa nhánh (đệ quy thực hiện nhiều hơn hai lần cho mỗi lần gọi lại) cũng có thể phân tích như đệ quy nhị phân với time complexity thông thường là O(n^x) với n là số lần thực hiện đệ quy cho mỗi lần gọi lại.

4.3. Đệ quy phi tuyến

4.3.1. Định nghĩa Đệ quy phi tuyến

Trong đệ quy phi tuyến, số lần một hàm gọi lại chính nó có thể thay đổi và không cố định, nó có thể phụ thuộc vào nhiều yếu tố khác nhau như giá trị đầu vào, điều kiện trong hàm, v.v.
Điều này tạo nên một cấu trúc phức tạp hơn so với đệ quy tuyến tính và nhị phân, nơi chúng ta có thể dự đoán trước được số lần gọi đệ quy ở mỗi bước.

4.3.2. Cấu trúc Đệ quy phi tuyến

  • Base Case: Điều kiện cơ bản để kết thúc quá trình đệ quy, tương đối giống với đệ quy tuyến tính.
  • Recursive Case: Phần của hàm nơi nó gọi lại chính nó
    Đối với trường hợp đệ quy phi tuyến, các trường hợp gọi lại tương đối phức tạp và khó đoán, mỗi lần gọi hàm sẽ thực hiện một số lượng không ổn định, tạo ra một cấu trúc cây tương đối phức tạp cả về chiền rộng lẫn chiều sâu.

4.3.3. Phân tích BigO

  • Space Complexity: Trong đệ quy phi tuyến, độ phức tạp không gian (space complexity) thường là O(n), do kiểu đệ quy này lưu trữ một thông tin dưới dạng cây.
    Tuy nhiên, vẫn có các trường hợp khác do nó còn phụ thuộc lớn và chiều sâu của cây và bài toán cần giải quyết.
  • Time Complexity: Vì mỗi lần gọi đệ quy, số lần thực hiện sẽ có độ biến thiên, vì thế độ phức tạp thời gian là sẽ được biểu diễn ở dạng O(x^n), nhưng còn phụ thuộc rất nhiều vào cách mà chúng ta xử lý ở mỗi lần gọi đệ quy.

4.4. Đệ quy lồng – Nested Recursion

4.4.1. Định nghĩa Đệ quy lồng

Đệ quy lồng (Nested Recursion) là một dạng đệ quy khi lời gọi đệ quy thực hiện với một tham số là kết quả của một lời gọi đệ quy khác.
Điều này tạo nên một cấu trúc đệ quy “lồng vào nhau” hoặc “đệ quy trong đệ quy”, khiến cho việc phân tích độ phức tạp cũng khó khăn hơn.

4.4.2. Cấu trúc Đệ quy lồng

  • Base Case: Điều kiện cơ bản để kết thúc quá trình đệ quy, tương đối giống với đệ quy tuyến tính. Đây là điều kiện là hàm gọi sẽ trả kết quả thay vì gọi một lồng đệ quy khác.
  • Recursive Case: Phần của hàm nơi nó gọi lại chính nó
    Trong trường hợp đệ quy, đệ quy lồng thể hiện sự phức tạp thông qua việc một lời gọi đệ quy có thể chứa một hoặc nhiều lời gọi đệ quy khác như một đối số.

4.4.3. Phân tích BigO

Do tính chất phức tạp tương tự với đệ quy phi tuyến, độ phức tạp thuật toán trong extra space và time complexity giống với đệ quy phi tuyến.

5. Một số bài toán sử dụng Đệ quy

5.1. Bài toán Fibonacci – Brute force

5.1.1. Định nghĩa bài toán Fibonacci – Brute force

Bài toán fibonacci là bài toán tìm số phần tử thứ n trong dãy số fibonacci. Sử dụng brute force là cách mà chúng ta tìm kiếm tất cả các trường hợp có thể xảy ra, và không sử dụng bất cứ một kỹ thuật nào để tối ưu thuật toán.
Dãy số fibonacci được định nghĩa như sau:
TEXT
copy
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) | n>2
Với bài toán này, đệ quy chúng ta sử dụng là đệ quy nhị phân, do mỗi lần gọi lại, hàm đệ quy gọi 2 lần đệ quy nhỏ hơn.

5.1.3. Hướng dẫn code và giải thích

TEXT
copy
F(0) = 0
F(1) = 1
Recursion case:
TEXT
copy
F(n) = F(n-1) + F(n-2) | n>2
Cùng phân tích một chút về đoạn code trên, với bài toán giả định chúng ta sử dụng fibonacci với input là 5.
Bài toán fibonacci với tham số bằng 5
GO
copy

package main

import “fmt”

func fibonacci(n int) int {
// base case
if n == 0 {
return 0
}
if n == 1 {
return 1
}

// recursion case
return fibonacci(n-1) + fibonacci(n-2)
}

func main() {
fmt.Println(fibonacci(5))
}

  • Bước 1: Tính F(5)
    Ở bước đầu tiên, để tìm giá trị F(5), chúng ta phải giải quyết hai bài toán nhỏ hơn, đó là F(4) và F(3).
  • Bước 2: Tính F(4) và F(3)
    Ở bước này, chúng ta cần tách biệt F(5) thành hai bài toán con:
    F(4) = F(3) + F(2)
    F(3) = F(2) + F(1)

    Tại bước này, bài toán thực hiện để quy 2 lần
    Như vậy, chúng ta sẽ tiếp tục giải quyết bộ bài toán nhỏ gồm F(3), F(2), F(2), và F(1).
  • Bước 3: Tính F(3), F(2), F(2) và F(1)
    Ở bước này, chúng ta sẽ tách F(3) thành F(2) và F(1), và tại thời điểm này, chúng ta đã thấy bắt đầu chạm đến các “base case”:

    F(3) = F(2) + F(1)
    F(2) = F(1) + F(0) = 1 + 0 = 1 | F(1) và F(0) là base case

    F(2) = F(1) + F(0) = 1 + 0 = 1 | F(1) và F(0) là base case
    F(1) = 1 | F(1) là base case
Tại bước này, số lương đệ quy đã tăng lên 4 lần gọi. Tuy nhiên, trong 4 lần gọi có 3 lần gọi đã chạm đến base case.
Giai đoạn sau, chúng ta chỉ cần tính toán một recursion case là F(3).
Tập hợp cần tính toán ở giai đoạn sau là F(2), F(1).
  • Bước 4: Tính F(2) và F(1)
    Ở bước này, chúng ta sẽ tách F(2), F(1) là base case nên không cần tính toán.
    F(2) = F(1) + F(0) = 1 + 0 = 1 | F(1) và F(0) là base case
    F(1) = 1 | F(1) là base case

    Cả 2 trường hợp đều là base case, dừng thực thi đệ quy.
Cuối cùng, tất cả các “base case” đã được đạt đến, kết thúc quá trình đệ quy và chúng ta có thể tổng hợp kết quả để tìm giá trị cuối cùng của F(5).

5.1.4. Phân tích Big(O)‌

  • Time complexity
    Vì bài toán này, mỗi bước chạy đệ quy sẽ gọi đến 2 đệ quy nhỏ hơn, do đó Big(O) về time sẽ là O(2^n). Điều này biểu thị một độ phức tạp rất lớn, đặc biệt khi n tăng lên.
  • Space extra
    Bài toán này không lưu thêm giá trị bên ngoài, do đó space extra là O(1).
Xét về mặt time complexity, do phải tính toán lại rất nhiều giá trị đã tính toán trước đó nên Big(O) của bài toán này là O(2^n). O(2^n) là một big(O) có độ phức tạp rất lớn, do đó cách triển khai này được nhận định là kém hiệu quả.

5.2. Bài toán Fibonacci – Memoization

5.2.1. Định nghĩa bài toán Fibonacci – Memoization

Với bài toán fibonacci sử dụng memoization, khi chúng ta tính toán được một giá trị, ta sẽ lưu tạm giá trị đó vào bộ nhớ, từ đó tránh được việc tính toán lại giá trị đã tính.
Nói ngắn gọn, bài toán con nào đã tính rồi, chúng ta sẽ lưu giá trị đó lại thay vì tính lại như phương pháp trên.

5.2.2. Phân tích cấu trúc bài toán Fibonacci – Memoization

Tham khảo hình 1 đính kèm.
Trong trường hợp này, trước khi thực hiện các lời gọi đệ quy, chúng ta sẽ kiểm tra xem kết quả cho n đã được tính toán chưa (tức là đã được lưu trong bảng memoization chưa). Nếu rồi, chúng ta chỉ cần lấy kết quả từ bảng ra mà không cần thực hiện lời gọi đệ quy.
Base case:
TEXT
copy
F(0) = 0
F(1) = 1
Recursion case:
TEXT
copy
F(n) = F(n-1) + F(n-2) | n>2
Tham khảo hình 2 đính kèm
Sử dụng kỹ thuật memoization để giảm số lần tính toán
5.2.3. Hướng dẫn code và giải thích
Tham khảo hình 6 đính kèm.
Cùng phân tích một chút về đoạn code trên, với bài toán giả định chúng ta sử dụng fibonacci với input là 5.
  • Bước 1: Tính F(5)
    Tại bước này, chúng ta cần tìm bài toán nhỏ hơn của 5, đó là F(4) và F(3).
  • Bước 2: Tính F(4) và F(3)
    Tại bước này, chúng ta cần tìm kiếm đồng thời 2 bài toán nhỏ hơn của F(5) là F(4) và F(3)
    F(4) = F(3) + F(2)
    F(3) = F(2) + F(1)
Tại bước này, bài toán thực hiện để quy 2 lần.
Tuy nhiên, do F(4) được gọi trước, nên chương trình sẽ tính toán thành công F(4) trước khi tính toán F(3).
Trong quá trình tính toán F(4) chúng ta sẽ lưu trữ dần các tham số fibonacci đã tính toán trước đó.
Do đó bước tính F(3) sẽ được lưu trong tham số mem nên không cần tính toán vào đệ quy nên bước này chỉ chạy đệ quy một lần.
Hàm F(5) sẽ có công thức như sau
F(4) = F(3) + F(2) | Lưu F(3) vào mem, F(2) được lấy từ mem khi tính F(3)
F(3) | F(3) được lấy từ mem

Bước sau, chúng ta sẽ tính toán F(3) và F(2)
  • Bước 3: Tính F(3), F(2)
    F(3) = F(2) + F(1) |Lưu F(2) vào mem
    F(2) | F(2) được lấy từ mem

    Tại bước này, số lương gọi đệ quy cũng chỉ là một do F(2) đã được lưu vào mem từ trước, lần call tới sẽ lấy từ mem.
  • Bước 4: Tính F(2)

    F(2) = F(1) + F(0) = 1 + 0 = 1 | F(1) và F(0) là base case
    Dừng thực thi đệ quy.
Tổng kết lại, chúng ta cần tính toán 4 bước, nhưng số lần gọi đệ quy ở mỗi bước chỉ là một lần, do chúng ta đã lưu thông tin tính toán được vào mem

5.1.4. Phân tích Big(O)‌

  • Time complexity
    Vì bài toán này, mỗi bước chạy đệ quy sẽ gọi duy nhất một lần do đó Big(O) về time sẽ là O(n)
  • Space extra
    Bài toán này buộc phải lưu thêm dữ liệu, chúng ta lưu từ F(3) đến F(n), do đó space extra là O(n)
Cách xử lý này cần lưu trữ thêm thông tin để làm bộ đệm, tuy nhiên nó giúp thời gian tính toán giảm xuống rất nhiều.
Tài liệu tham khảo:
https://en.wikipedia.org/wiki/Recursion_(computer_science)
https://en.wikipedia.org/wiki/Fibonacci_sequence
https://www.geeksforgeeks.org/types-of-recursions/
https://en.wikipedia.org/wiki/Big_O_notation
Share.