Giới thiệu về Đệ quy
Đệ quy là một khái niệm cơ bản và mạnh mẽ trong các thuật toán máy tính, thường được sử dụng để giải quyết các vấn đề có thể phân rã thành các bài toán con nhỏ hơn, tương tự nhau. Các thuật toán nổi tiếng như QuickSort và MergeSort là những ví dụ điển hình về ứng dụng của đệ quy. Mặc dù rất hiệu quả, việc viết mã đệ quy chính xác và tối ưu có thể khá thách thức, bởi lẽ nó dễ dẫn đến các lỗi như vòng lặp vô hạn hoặc tràn bộ nhớ stack nếu không được xử lý cẩn thận. Để thành thạo đệ quy, ba nguyên tắc cốt lõi sau đây là không thể thiếu:
- Xác định Bài toán Con (Tính tự tương tự): Nhận diện cách một vấn đề lớn có thể được biểu diễn dưới dạng các phiên bản nhỏ hơn của chính nó. Điều này đòi hỏi khả năng nhìn ra các vấn đề con trùng lặp hoặc có cấu trúc tương tự.
- Trường hợp Cơ sở (Base Case): Thiết lập một hoặc nhiều điều kiện dừng để kết thúc quá trình đệ quy và cung cấp một giải pháp trực tiếp, từ đó ngăn chặn các vòng lặp vô hạn.
- Quản lý Trạng thái (Bảo toàn Ngữ cảnh): Đảm bảo rằng trạng thái hiện tại (ví dụ: các biến, các lựa chọn đã thực hiện) được truyền đúng cách cho các lời gọi đệ quy tiếp theo và được khôi phục khi lời gọi đệ quy hoàn tất, đặc biệt quan trọng trong các kịch bản quay lui (backtracking).
Lấy ví dụ với QuickSort: bài toán sắp xếp một mảng có thể được quy về việc sắp xếp hai mảng con ở hai bên một phần tử chốt. Trường hợp cơ sở là khi mảng con có không hoặc một phần tử.
Các Bài Toán Kinh Điển về Đệ quy
1. Bài toán Tập con (Subsets)
Cho một mảng số nguyên nums chứa các phần tử đôi một khác nhau, hãy trả về tất cả các tập con có thể có của mảng đó. Tập kết quả không được chứa các tập con trùng lặp. Thứ tự của các tập con trong kết quả có thể theo bất kỳ cách nào.
Ví dụ 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Cách tiếp cận 1: Xây dựng tập con theo độ dài
Một cách để tạo tất cả các tập con là duyệt qua tất cả các độ dài tập con có thể (từ 0 đến len(nums)) và sử dụng đệ quy để tìm các tập con có độ dài đó. Hàm đệ quy sẽ chọn các phần tử lần lượt, đảm bảo tính duy nhất và thứ tự tăng dần.
package main
import "fmt"
// generateSubsetsByLength tìm tất cả các tập con của một mảng số nguyên,
// xây dựng các tập con dựa trên độ dài mong muốn.
func generateSubsetsByLength(numbers []int) [][]int {
var allSubsets [][]int // Kết quả cuối cùng chứa tất cả các tập con
currentSubset := make([]int, 0) // Tập con hiện tại đang được xây dựng
var findSubsets func(startIdx int, targetLength int)
findSubsets = func(startIdx int, targetLength int) {
// Trường hợp cơ sở: nếu độ dài tập con hiện tại đã đạt đến độ dài mục tiêu
if len(currentSubset) == targetLength {
// Thêm bản sao của tập con này vào kết quả
tempSubset := make([]int, len(currentSubset))
copy(tempSubset, currentSubset)
allSubsets = append(allSubsets, tempSubset)
return
}
// Vòng lặp để chọn các phần tử cho tập con
for i := startIdx; i < len(numbers); i++ {
currentSubset = append(currentSubset, numbers[i]) // Chọn phần tử
findSubsets(i + 1, targetLength) // Đệ quy với chỉ mục tiếp theo
currentSubset = currentSubset[:len(currentSubset)-1] // Quay lui: loại bỏ phần tử đã chọn
}
}
// Duyệt qua tất cả các độ dài tập con có thể (từ 0 đến len(numbers))
for l := 0; l <= len(numbers); l++ {
currentSubset = []int{} // Đặt lại tập con hiện tại cho mỗi độ dài
findSubsets(0, l) // Bắt đầu tìm kiếm tập con có độ dài 'l'
}
return allSubsets
}
Cách tiếp cận 2: Chọn hoặc Không chọn (Pick/Don't Pick)
Cách tiếp cận phổ biến hơn là duyệt qua từng phần tử trong mảng và tại mỗi bước, chúng ta có hai lựa chọn: bao gồm phần tử hiện tại vào tập con hoặc không bao gồm nó. Đây là một mô hình đệ quy nhị phân.
package main
import "fmt"
// generateSubsetsBinary tìm tất cả các tập con của một mảng số nguyên
// bằng cách sử dụng chiến lược chọn/không chọn cho mỗi phần tử.
func generateSubsetsBinary(numbers []int) [][]int {
var allResults [][]int // Danh sách các tập con cuối cùng
currentSelection := make([]int, 0) // Tập con đang được xây dựng
var explore func(index int)
explore = func(index int) {
// Trường hợp cơ sở: đã duyệt qua tất cả các phần tử trong mảng
if index == len(numbers) {
// Thêm bản sao của tập con hiện tại vào danh sách kết quả
temp := make([]int, len(currentSelection))
copy(temp, currentSelection)
allResults = append(allResults, temp)
return
}
// Lựa chọn 1: KHÔNG bao gồm số tại 'index' vào tập con hiện tại
explore(index + 1)
// Lựa chọn 2: BAO GỒM số tại 'index' vào tập con hiện tại
currentSelection = append(currentSelection, numbers[index]) // Thêm phần tử
explore(index + 1) // Đệ quy
currentSelection = currentSelection[:len(currentSelection)-1] // Quay lui: loại bỏ phần tử để khôi phục trạng thái
}
explore(0) // Bắt đầu quá trình khám phá từ phần tử đầu tiên (index 0)
return allResults
}
2. Bài toán Tổ hợp (Combinations)
Cho hai số nguyên n và k, hãy tìm tất cả các tổ hợp gồm k số có thể có từ tập hợp các số từ 1 đến n.
Ví dụ 1:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Cách tiếp cận 1: Quay lui (Backtracking) với chỉ mục bắt đầu
Chúng ta có thể sử dụng phương pháp quay lui để xây dựng các tổ hợp. Tại mỗi bước, chúng ta chọn một số từ startIndex đến n và sau đó đệ quy để tìm các số tiếp theo từ i+1. Điều này đảm bảo rằng các tổ hợp không có phần tử lặp lại và các phần tử trong mỗi tổ hợp được sắp xếp tăng dần.
package main
import "fmt"
// combinationsFinder tìm tất cả các tổ hợp gồm k số từ tập hợp [1, n].
func combinationsFinder(n int, k int) [][]int {
var results [][]int // Danh sách các tổ hợp cuối cùng
currentCombination := make([]int, 0, k) // Tổ hợp hiện tại đang được xây dựng
var exploreCombinations func(startIndex int)
exploreCombinations = func(startIndex int) {
// Trường hợp cơ sở: nếu tổ hợp hiện tại đã đủ k phần tử
if len(currentCombination) == k {
validCombination := make([]int, k)
copy(validCombination, currentCombination)
results = append(results, validCombination)
return
}
// Cắt tỉa (Pruning): nếu số phần tử còn lại không đủ để tạo thành một tổ hợp k phần tử
// Số phần tử cần thêm: k - len(currentCombination)
// Số phần tử còn có thể chọn: n - startIndex + 1
if k-len(currentCombination) > n-startIndex+1 {
return
}
// Duyệt qua các số từ startIndex đến n
for num := startIndex; num <= n; num++ {
currentCombination = append(currentCombination, num) // Chọn số 'num'
exploreCombinations(num + 1) // Đệ quy, bắt đầu tìm số tiếp theo từ 'num + 1'
currentCombination = currentCombination[:len(currentCombination)-1] // Quay lui: loại bỏ số 'num'
}
}
exploreCombinations(1) // Bắt đầu quá trình khám phá từ số 1
return results
}
Cách tiếp cận 2: Chọn hoặc Không chọn với Cắt tỉa
Tương tự như bài toán tập con, chúng ta có thể áp dụng mô hình chọn/không chọn. Tuy nhiên, với bài toán tổ hợp, chúng ta có thể thêm các điều kiện cắt tỉa (pruning) để loại bỏ các nhánh không khả thi của cây đệ quy sớm hơn.
package main
import "fmt"
// findCombinationsBinary tìm tất cả các tổ hợp gồm k số từ [1, n]
// bằng cách sử dụng phương pháp chọn/không chọn.
func findCombinationsBinary(n int, k int) [][]int {
var results [][]int // Danh sách các tổ hợp cuối cùng
currentElements := make([]int, 0, k) // Tổ hợp hiện tại đang được xây dựng
var recursiveSolver func(currentIndex int)
recursiveSolver = func(currentIndex int) {
// Cắt tỉa:
// 1. Nếu số lượng phần tử đã chọn vượt quá k
// 2. Hoặc nếu số lượng phần tử còn lại cộng với số đã chọn không đủ k
if len(currentElements) > k || len(currentElements)+(n-currentIndex+1) < k {
return
}
// Trường hợp cơ sở: đã xử lý tất cả các số từ 1 đến n
if currentIndex == n+1 {
// Nếu tổ hợp hiện tại có đúng k phần tử, thêm vào kết quả
if len(currentElements) == k {
finalCombo := make([]int, k)
copy(finalCombo, currentElements)
results = append(results, finalCombo)
}
return
}
// Lựa chọn 1: KHÔNG bao gồm số tại 'currentIndex'
recursiveSolver(currentIndex + 1)
// Lựa chọn 2: BAO GỒM số tại 'currentIndex'
currentElements = append(currentElements, currentIndex) // Thêm
recursiveSolver(currentIndex + 1) // Đệ quy
currentElements = currentElements[:len(currentElements)-1] // Quay lui: loại bỏ
}
recursiveSolver(1) // Bắt đầu với số 1
return results
}
3. Bài toán Hoán vị (Permutations)
Cho một mảng nums gồm các số nguyên không trùng lặp, hãy trả về tất cả các hoán vị có thể có của mảng đó. Thứ tự của các hoán vị trong kết quả có thể tùy ý.
Ví dụ 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Bài toán hoán vị yêu cầu sắp xếp tất cả các phần tử theo mọi cách có thể. Chúng ta sẽ sử dụng phương pháp quay lui kết hợp với một mảng đánh dấu các phần tử đã được sử dụng để tránh lặp lại và tạo ra các hoán vị duy nhất.
package main
import "fmt"
// generatePermutations tìm tất cả các hoán vị có thể có của mảng numbers.
func generatePermutations(numbers []int) [][]int {
var allPermutations [][]int // Danh sách các hoán vị cuối cùng
currentPermutation := make([]int, 0, len(numbers)) // Hoán vị hiện tại đang được xây dựng
visited := make([]bool, len(numbers)) // Mảng boolean để theo dõi các chỉ mục đã được thăm
var backtrack func()
backtrack = func() {
// Trường hợp cơ sở: nếu hoán vị hiện tại đã đủ độ dài của mảng gốc
if len(currentPermutation) == len(numbers) {
// Thêm bản sao của hoán vị hoàn chỉnh vào danh sách kết quả
validPermutation := make([]int, len(numbers))
copy(validPermutation, currentPermutation)
allPermutations = append(allPermutations, validPermutation)
return
}
// Duyệt qua tất cả các phần tử trong mảng gốc
for i := 0; i < len(numbers); i++ {
// Nếu phần tử tại chỉ mục 'i' chưa được sử dụng
if !visited[i] {
visited[i] = true // Đánh dấu đã sử dụng
currentPermutation = append(currentPermutation, numbers[i]) // Thêm vào hoán vị hiện tại
backtrack() // Đệ quy
currentPermutation = currentPermutation[:len(currentPermutation)-1] // Quay lui: loại bỏ phần tử cuối cùng
visited[i] = false // Quay lui: bỏ đánh dấu đã sử dụng
}
}
}
backtrack() // Bắt đầu quá trình quay lui
return allPermutations
}