MapInfo Pro Developers User Group

Recursive functions in MapBasic

  • 1.  Recursive functions in MapBasic

    Posted 09-28-2018 11:50
      |   view attached

    In this short article we will take a look at recursive functions in MapBasic

    What is a recursive function?

    A recursive function is basically a function that calls itself to get a job done.

    A recursive function is often used if the job at hand can be split into smaller pieces and process using the same function.

    A couple of examples of a recursive functions:

    Search & Replace.

    When you need to search a string for a substring and replace that with a new string, you can split this into smaller pieces.

    Often the result will be a smaller function that if you try to handle the entire process in the function.

    1. Find the first instance of the substring and replace it with the new string. So this process will only replace the first instance and to find the next, you can call the function again, either with the entire modified string or only with the remaining string.
    2. Divide a square into four new squares until the number of points with the square is less than a certain value.

     

    Notice that mostly the process of a recursive function can also be done using some sort of a loop structure.

    How do I use it?

    Let us dive a bit into the second example and look at the structure of it.

    The basic input is a square - or a MBR, a minimum bounding rectangle - that you want to subdivide if it holds too many points.

    Pseudocode for the function could look like this:

    Subdivide(oMBR)

    If PointInMBR(oMBR) > nMaximumPoints Then

    ***Split the MBR into four new MBRs

    Call Subdivide(LowerLeftMBR(oMBR))

    Call Subdivide(UpperLeftMBR(oMBR))

    Call Subdivide(UpperRightMBR(oMBR))

    Call Subdivide(LowerRightMBR(oMBR))

    Else

    Call StoreMBR(oMBR)

    End If

    End Function

    As you can see here - where simple code and no looping at all. The code only checks if the numbe rof points inside the MBR is over or under the maximum allowed. If too many points, the MBR is split and the same function is called four times each with the new subdivide MBR.

    I have include a file with the similar MapBasic code which is a big bigger. But it's working and should be fairly easy to read and understand.

    Here is a map showing hwo the resulting squares will look. In areas with many points, the squares will be small compared to areas with fewer points.

    See Attachment

    Some traps to try to avoid

    You need to consider what might go wrong or if there is cases where you "stop" condition might never be met. And so, you need to handle these specific cases in your code.

    For the splitting, you might want to limit the size of the resulting MBR. This can be done be maing sure you don't go to deep into the recursive functions by checking how many times it has been called. I have build such a validation into the MapBasic source code.

    Any question, feel free to post them as comments