Recursive method

From REALbasicWiki

Overall article skill

✭

A recursive method is a method which calls itself.

See recursion (computer science) on Wikipedia.

[edit] Example

An example of a recursive method is given in Delete a non-empty folder.

[edit] MergeSort

A classic example of an algorithm that uses a recursive method is mergesort (see merge sort on Wikipedia - not for beginners).

Given two sorted lists, there is an obvious algorithm to merge them into a single sorted list -- compare the first item of each list, and move the smaller of the two to the new list.

Function Merge(a() as String, b() as String) as String()
  dim c() as String
  
  dim X as Integer = 0
  dim Y as Integer = 0
  
  do
    if X > UBound(a) then
      for i as Integer = Y to UBound(b)
        c.Append b(i)
      next
      exit
    end if
    if Y > UBound(b) then
      for i as Integer = X to UBound(a)
        c.Append a(i)
      next
      exit
    end if
    
    if a(X) <= b(Y) then
      c.Append a(X)
      X = X + 1
    else
      c.Append b(Y)
      Y = Y + 1
    end if
  loop
  Return c
End Function

With this function, we can now define a simple and fast sorting algorithm: given an array, split it into two arrays. Sort each array, then merge the two.

Function MergeSort(s() as String) as String()
  if UBound(s) <= 0 then //s is sorted
    return s
  end if
  
  dim midpoint as Integer = UBound(s)\2
  dim a() as String
  for i as Integer = 0 to midpoint
    a.Append s(i)
  next
  
  dim b() as String
  for i as Integer = midpoint + 1 to UBound(s)
    b.Append s(i)
  next
  
  return Merge(MergeSort(a), MergeSort(b))
End Function