Thuật toán "Đệ Quy"

[Nguyễn Duy Tuân]

Thuật toán đệ quy đã có nhiều sách vở nói đến, có thể dễ dàng google là ra rất nhiều. Trên GPE cũng có thể nhiều bạn chưa biết hay đã biết. Tôi xin đưa ra để mọi người hiểu và cùng thảo luận thêm.

Có nhiều khái niệm về Đệ quy. Tôi xin nói theo cách hiểu của mình như thế này. Đệ quy là việc chạy lại một hàm hay thủ tục trong chính nó.

Ví dụ: Tinh giai thừa của một số bất kỳ
Cách dùng vòng lặp

Function GiaiThua2(ByVal SoNguyen As Long) As Long
    Dim I As Long
    GiaiThua2 = 1
    For I = SoNguyen To 1 Step -1
        GiaiThua2 = GiaiThua2 * I
    Next I
End Function

GiaiThua2 = GiaiThua2 * I. GiaiThua2 trong dòng lệnh này đóng vai trò như một biến .

Dùng Đệ quy

Function [B]GiaiThua[/B](ByVal SoNguyen As Long) As Long
[COLOR="SeaGreen"]    'GiaiThua(5) = 5*4*3*2*1
    'SoNguyen! = SoNguyen * (SoNguyen-1) * (SoNguyen-2)*...*1[/COLOR]
    If SoNguyen = 1 Or SoNguyen = 0 Then
        GiaiThua = 1
    Else
        GiaiThua = SoNguyen * [B]GiaiThua[/B](SoNguyen - 1)
    End If
    
End Function

GiaiThua = SoNguyen * GiaiThua(SoNguyen - 1). GiaiThua(SoNguyen - 1) được gọi lại với một tham số mới. Đây chính là thuật Đệ quy!
Ví dụ 2: Nhập số. Yếu cầu nhập số, nếu nhập sai thì nhập lại.
Dùng vòng lặp

Sub NhanSo2()
    Dim vSo As Variant
    vSo = "ABC"
    Do While True
        If Not IsNumeric(vSo) Then
            vSo = InputBox("Hay nhap mot so. Neu nhap sai chuong trinh yeu cau nhap lai!", "Nhan So")
        Else
            MsgBox "Ban da nhap dung!"
            Exit Do
        End If
    Loop
    
End Sub

Dùng Đệ quy

Sub [B]NhanSo[/B]()
    Dim vSo As Variant
    vSo = InputBox("Hay nhap mot so. Neu nhap sai chuong trinh yeu cau nhap lai!", "Nhan So")
    If Not IsNumeric(vSo) Then
        [B]NhanSo[/B]
    Else
        MsgBox "Ban da nhap dung!"
    End If
End Sub

Mình đang viết dở thì bận rồi, xin viết tiếp bài sau.

 

[lypt]

Các bạn khác có thể lục lại các tình huống tính toán nào có dạnh Đệ quy không? Nếu có chúng ta đem lên để thực hiện.

(1) Một số người mua vé số, đánh lô đề, hay xem số điện thoại thường quan tâm việc số đó có phải là số gánh. Hoặc có một chuỗi ký tự không biết rõ nó có đối xứng hay không. Việc xem xét số gánh hay chuỗi ký tự đối xứng như trên có thể được giải quyết bằng cách tạo chuỗi số hoặc chuỗi ký tự ngược và xét chuỗi xuôi-ngược có bằng nhau không, hoặc tạo vòng lặp để xem xét số hay ký tự đầu-đuôi cách đều tương ứng có bằng nhau không. Tuy nhiên, có một phương pháp giải quyết đề bài trên theo phương thức “đệ quy” nêu ở đây. Mời các bạn xem code và file đính kèm.

 Function DX(ByVal T As String) As Variant
  If Len(T) > 1 Then
      If Left(T, 1) <> Right(T, 1) Then
          DX = "KHONG"
          Exit Function
      Else
          DX = DX(Mid(T, 2, Len(T) - 1))
      End If
  End If
  DX = "DOI XUNG"
  End Function

(2) Theo tôi biết, trong thống kê phân tích dữ liệu, có phương pháp dự báo gọi là ARIMA. ARIMA có thể áp dụng trong dự báo ngắn hạn về giá chứng khoán, giá vàng, giá đô la, …Hàm dự báo theo phương pháp ARIMA thường có dạng P(n) = a0 + a1.P(n-1) + a2.P(n-2) + a3.P(n-3) với a0, a1, a2, a3 là các hệ số tính theo hồi quy ARIMA. Theo như hàm trên thì có thể áp dụng đệ quy để dự báo giá trong tương lai thông qua việc có trước giá của 3 kỳ liên tiếp. Trích một đoạn code có thể là :
If n=1 then GiaDuBao=P1 '(P1 là số cụ thể)
If n=2 then GiaDuBao=P2 '(P2 là số cụ thể)
If n=3 then GiaDuBao=P3 '(P3 là số cụ thể)
If n>3 then GiaDuBao= a0 + a1*P(n-1) + a2*P(n-2) + a3*P(n-3) 'a0, a1, a2, a3 là số cụ thể

 

[Nguyễn Duy Tuân]

2) liệt kê các thư mục con trong một thư mục xác định (Cách 2)

2) Liệt kê các thư mục con trong một thư mục xác định (Cách 2)

Tôi đưa ra cách 2 không dùng tới Shell.Application mà dùng hàm Dir của VB các bạn tham khảo thêm.

[COLOR="SeaGreen"]'For Unicode function[/COLOR]
Private Const FILE_ATTRIBUTE_DIRECTORY = &H10
Private Declare Function GetFileAttributes Lib "kernel32" Alias "GetFileAttributesW" (ByVal lpFileName As String) As Long
[COLOR="SeaGreen"]'-----------------------------------------------------------------------------------[/COLOR]
Sub LoadAllFolder()
    Dim RowIndex As Long, FirstPath As String
    FirstPath = InputBox("Fullpath:", "LoadAllFolder", CurDir)
    If Dir(FirstPath, vbDirectory) = "" Then
        MsgBox """" & FirstPath & """ is not a folder.", vbCritical, "LoadAllFolder"
        Exit Sub
    End If
    RowIndex = 0
    LoadFolder FirstPath, RowIndex
End Sub

[COLOR="SeaGreen"]'-----------------------------------------------------------------------------------[/COLOR]
Sub LoadFolder(ByVal Path As String, ByRef RowIndex As Long)
    
    Dim aFolders(), FolderCount As Long, I As Long
    
    FolderCount = GetSubFolders(Path, aFolders)
    For I = 1 To FolderCount
        [COLOR="SeaGreen"]'Excel Range[/COLOR]
        RowIndex = RowIndex + 1 'For Next row
        Cells(RowIndex, 1).Value = aFolders(I)
        [COLOR="SeaGreen"]'De quy[/COLOR]
        LoadFolder aFolders(I) & "\", RowIndex
    Next I
    
End Sub
[COLOR="SeaGreen"]'-----------------------------------------------------------------------------------[/COLOR]
Function GetSubFolders(ByVal Path As String, ByRef aFolders()) As Long
    On Error GoTo EndFunc
    Dim FolderName As String, SubPath As String
    
    GetSubFolders = 0
    
    If Right(Path, 1) <> "\" Then Path = Path + "\"
    
    FolderName = Dir(Path, vbDirectory)
    
    Do While FolderName <> ""   ' Start the loop.
        [COLOR="SeaGreen"]'Ignore the current directory and the encompassing directory.[/COLOR]
        If FolderName <> "." And FolderName <> ".." Then
            SubPath = Path & FolderName
           [COLOR="SeaGreen"] ' Use bitwise comparison to make sure SubPath is a directory.[/COLOR]
            If IsFolder(SubPath) Then
                GetSubFolders = GetSubFolders + 1
                ReDim Preserve aFolders(GetSubFolders)
                aFolders(GetSubFolders) = SubPath
            Else
                [COLOR="SeaGreen"]'Is a File (FullName)[/COLOR]
            End If   [COLOR="SeaGreen"] ' it represents a directory.[/COLOR]
        End If
        FolderName = Dir  [COLOR="SeaGreen"] ' Get next entry.[/COLOR]
    Loop
    
EndFunc:
End Function
[COLOR="SeaGreen"]'-----------------------------------------------------------------------------------[/COLOR]
Function IsFolder(ByVal Path As String) As Boolean
    Path = StrConv(Path, vbUnicode)
    IsFolder = (GetFileAttributes(Path) And FILE_ATTRIBUTE_DIRECTORY) = FILE_ATTRIBUTE_DIRECTORY
End Function

Tôi gửi file về các ví dụ trên, các bạn tham khảo.

 

[haonlh]

Theo tôi
Thuật toán đệ quy là để giải quyết các bài toán được định nghĩa theo kiểu đệ quy, sao cho nhìn mã nguồn, người ta vẫn thấy nó gần gũi với định nghĩa. Ví dụ
n! = 1 nếu n=1 hoặc n = 0
n*(n-1) với n>1
hoặc định nghĩa dãy Fibonaxi: cho a(1) = a(2) = 1, với n>2, a(n) = a(n-1) + a(n-2) (tôi dùng chỉ số trong ngoặc tròn vì không biết cách viết chỉ số dưới trong GPE, hơn nữa coi như hàm a(x) với đối số trên tập số nguyên dương).
Nếu vội, hoặc chương trình nhỏ ta cứ dùng đệ quy. Còn nếu có thể, hoặc đệ quy lớn, ta nên chuyển sang các loại vòng lặp. Vì mỗi lần gọi đệ quy, tài nguyên của máy như RAM sẽ bị dùng nhiều hơn. Ai biết chạy theo vết, biết mở Stack thì thấy.
Ví dụ: Nếu viết chương trình đệ quy bằng dùng khai triển định thức của ma trận vuông cấp n bằng cách tính n định thức cấp (n - 1) (hình như là định lý Laplace), và định thức của ma trận vuông cấp 1 là chính giá trị số của ma trận đó (theo đúng định nghĩa định thức của ma trận đó) thì cũng hay đó. Nhưng với n đủ lớn, Stack tràn, chương trình bị Break.