Loop vs Recursion


First Published 29 Dec 2022                                                                                                                                             Difficulty level :   Moderate

Section Links:
        Introduction
        Tests / Results
        Additional Tests / Results (large dataset)
        Download
        Conclusions
        Further Reading
        Feedback



1.   Introduction                                                                                                                                         Return To Top

      This is the fourteenth in a series of articles discussing various tests done to compare the efficiency of different approaches to coding.

      The article was inspired by a reader challenge at the NoLongerSet website run by fellow MVP Mike Wolfe on 22 Dec 2022:

      How many total gifts does one's true love deliver by the Nth day of Christmas?

On The First Day Of Christmas
My True Love Sent To Me:
A Partridge In A Pear Tree

On The Second Day Of Christmas
My True Love Sent To Me:
Two Turtle Doves
And A Partridge In A Pear Tree
On The Third Day Of Christmas
My True Love Sent To Me:
Three French Hens
Two Turtle Doves
And A Partridge In A Pear Tree

On The Fourth Day Of Christmas
My True Love Sent To Me:
Four Calling Birds
Three French Hens
Two Turtle Doves
And A Partridge In A Pear Tree

On The Fifth Day Of Christmas
My True Love Sent To Me:
Five Golden Rings
Four Calling Birds
Three French Hens
Two Turtle Doves
And A Partridge In A Pear Tree

On The Sixth Day Of Christmas
My True Love Sent To Me:
Six Geese A Laying
Five Golden Rings
Four Calling Birds
Three French Hens
Two Turtle Doves
And A Partridge In A Pear Tree

On The Seventh Day Of Christmas
My True Love Sent To Me:
Seven Swans A Swimming
Six Geese A Laying
Five Golden Rings
Four Calling Birds
Three French Hens
Two Turtle Doves
And A Partridge In A Pear Tree

On The Eighth Day Of Christmas
My True Love Sent To Me:
Eight Maids A Milking
Seven Swans A Swimming
Six Geese A Laying
Five Golden Rings
Four Calling Birds
Three French Hens
Two Turtle Doves
And A Partridge In A Pear Tree

On The Ninth Day Of Christmas
My True Love Sent To Me:
Nine Ladies Dancing
Eight Maids A Milking
Seven Swans A Swimming
Six Geese A Laying
Five Golden Rings
Four Calling Birds
Three French Hens
Two Turtle Doves
And A Partridge In A Pear Tree

On The Tenth Day Of Christmas
My True Love Sent To Me:
Ten Lords A Leaping
Nine Ladies Dancing
Eight Maids A Milking
Seven Swans A Swimming
Six Geese A Laying
Five Golden Rings
Four Calling Birds
Three French Hens
Two Turtle Doves
And A Partridge In A Pear Tree

On The Eleventh Day Of Christmas
My True Love Sent To Me:
Eleven Pipers Piping
Ten Lords A Leaping
Nine Ladies Dancing
Eight Maids A Milking
Seven Swans A Swimming
Six Geese A Laying
Five Golden Rings
Four Calling Birds
Three French Hens
Two Turtle Doves
And A Partridge In A Pear Tree

On The Twelfth Day Of Christmas
My True Love Sent To Me:
12 Drummers Drumming
Eleven Pipers Piping
Ten Lords A Leaping
Nine Ladies Dancing
Eight Maids A Milking
Seven Swans A Swimming
Six Geese A Laying
Five Golden Rings
Four Calling Birds
Three French Hens
Two Turtle Doves
And A Partridge In A Pear Tree



      Here is an image taken from Mike's article:


      Mike then published two solutions in subsequent days - the first looping through the data and the second using recursion.
      NOTE: A recursive function calls itself. An example in mathematics is a factorial e.g. 5 factorial (or 5!) = 5x4x3x2x1 = 120

      Having just completed comparing the use of Regex vs Loop, I thought that recursion would be faster for this simple task. I was wrong!

      This is Mike's code for each approach:

a)   LOOP

'https://nolongerset.com/gift-counts-looping-solution/

Function LoopGiftsByXmasDay(DayOfXmas As Long) As Long

      'Initialise x & y
      Dim x As Long: x = DayOfXmas
      Dim y As Long: y = 1
      Dim i As Integer

      For i = 1 To DayOfXmas
            LoopGiftsByXmasDay = LoopGiftsByXmasDay + x * y
            x = x - 1 'Decrement x
            y = y + 1 'Increment y
      Next i

End Function

b)   RECURSION

'https://nolongerset.com/gift-counts-recursion-solution/

Function RecursionGiftsByXmasDay(DayOfXmas As Long) As Long

      'Calculate the number of gifts given for the current day
      Dim GiftsThisDay As Long, NumberOfItems As Long

      For NumberOfItems = 1 To DayOfXmas
            GiftsThisDay = GiftsThisDay + NumberOfItems
      Next NumberOfItems

      If DayOfXmas > 1 Then
            'Use recursion to call the function for each previous day
            RecursionGiftsByXmasDay = GiftsThisDay + RecursionGiftsByXmasDay(DayOfXmas - 1)
      Else
            'With recursion you always need a code path where the function does not call itself,
            ' otherwise you end up with infinite recursion and out of stack space' errors
            RecursionGiftsByXmasDay = 1
      End If

End Function

2.   Tests / Results                                                                                                                                   Return To Top

      I created a simple procedure to compare the speed of each approach
      With such a small dataset, each test was so fast that I cycled through each test 100,000 times to get a measurable result.

Function SpeedTests1(D As Long)

      'Time the loop and recursion tests where D = number of days
      Dim dblStart As Double, dblEnd As Double
      Dim lngCount As Long, N As Long, T As Double

      Debug.Print "Days 1 to " & D & ": 100000 runs"

      dblStart = Timer
      For lngCount = 1 To 100000
            For N = 1 To D       T = total gifts after D days
                  LoopGiftsByXmasDay (N)
            Next N
      Next lngCount

      T = LoopGiftsByXmasDay(D)

      dblEnd = Timer
      Debug.Print "1. LoopGiftsByXmasDay", "Total Days = " & N - 1, "Total Gifts = " & T, _
            "Time Taken = " & dblEnd - dblStart & " s "

      '======================================

      dblStart = Timer
      For lngCount = 1 To 100000
            For N = 1 To D
                  RecursionGiftsByXmasDay (N)
            Next N
      Next lngCount

      T = RecursionGiftsByXmasDay(D)       T = total gifts after D days

      dblEnd = Timer
      Debug.Print "2. RecursionGiftsByXmasDay", "Total Days = " & N - 1, "Total Gifts = " & T, _
            "Time Taken = " & dblEnd - dblStart & " s "

      Debug.Print ""

End Function

      Here are a selection of my results from the Immediate window:


      As you can see, the recursion results are NEVER faster with the additional time required increasing significantly as the number of days increased.



3.   Additional Tests / Results (larger dataset)                                                                                         Return To Top

      Following an exchange of comments in the third article in this series (and before I revealed my test results), Mike asked whether it would make any
      difference if a 'lifetime' of gifts were tested where a 'lifetime' was defined as 100,000 days - approx 285 years!

      It was clear that the pattern would continue with recursion becoming increasingly slow
      It was also obvious that the out of stack space error would occur at some point using recursion.

      I modified the code slightly in order to handle the much larger numbers involved.
      I also decided to run each test once rather than cycling through repeatedly as before

      Here is the amended code:

a)   LOOP

LoopGiftsLifetime(DayOfLifetime As Long) As Double

      'Initialise x & y
      Dim x As Long: x = DayOfLifetime
      Dim y As Long: y = 1
      Dim i As Integer

      For i = 1 To DayOfLifetime
            LoopGiftsLifetime = LoopGiftsLifetime + x * y
            x = x - 1 'Decrement x
            y = y + 1 'Increment y
      Next i

End Function

b)   RECURSION

Function RecursionGiftsLifetime(DayOfLifetime As Long) As Double

      'Calculate the number of gifts given for the current day
      Dim GiftsThisDay As Long, NumberOfItems As Double

      For NumberOfItems = 1 To DayOfXmas
            GiftsThisDay = GiftsThisDay + NumberOfItems
      Next NumberOfItems

      If DayOfLifetime > 1 Then
            'Use recursion to call the function for each previous day
            RecursionGiftsLifetime = GiftsThisDay + RecursionGiftsLifetime(DayOfLifetime - 1)
      Else
            'With recursion you always need a code path where the function does not call itself,
            ' otherwise you end up with infinite recursion and out of stack space' errors
            RecursionGiftsLifetime = 1
      End If

End Function

      This is the updated speed test function

Function SpeedTests2(D As Long)

      'Time the loop and recursion tests where D = number of days
      Dim dblStart As Double, dblEnd As Double
      Dim N As Long, T As Double

      Debug.Print "Days 1 to " & D & ": 1 run"

      dblStart = Timer
      For N = 1 To D       T = total gifts after D days
            LoopGiftsByXmasDay (N)
      Next N

      T = LoopGiftsByXmasDay(D)

      dblEnd = Timer
      Debug.Print "1. LoopGiftsByXmasDay", "Total Days = " & N - 1, "Total Gifts = " & T, _
            "Time Taken = " & dblEnd - dblStart & " s "

      '======================================

      dblStart = Timer
      For N = 1 To D
            RecursionGiftsByXmasDay (N)
      Next N

      T = RecursionGiftsByXmasDay(D)       T = total gifts after D days

      dblEnd = Timer
      Debug.Print "2. RecursionGiftsByXmasDay", "Total Days = " & N - 1, "Total Gifts = " & T, _
            "Time Taken = " & dblEnd - dblStart & " s "

      Debug.Print ""

End Function

      Here are a selection of my results from the Immediate window:


      During these tests, I checked the CPU, memory and power usage in the Task Manager.
      All were VERY HIGH throughout the recursion tests and Access stopped responding for a significant time


      Even so, I was surprised to run out of stack space after just 5000 days!


      NOTE: All tests were run using 64-bit Windows 10 with 32-bit A365 with 16 GB RAM



4.   Download                                                                                                                                             Return To Top

      Click to download the example database with all code in these tests.

      Loop vs Recursion      Approx 0.4 MB (zipped)



5.   Conclusions                                                                                                                                           Return To Top

      Recursion is a powerful approach to coding that is extremely useful in certain situations e.g. hierarchical tasks such as genealogy
      However, it tends to be 'expensive' in terms of the processing power needed
      You should THOROUGHLY test it before distributing applications for end users

      Looping is generally simpler to code and less demanding on processing power
      In this particular example, looping worked well. However, in another recent set of tests, Regex Or Not, it performed badly.

      Developers should always aim to choose the best tool for the task in hand.



6.   Further Reading                                                                                                                               Return To Top

      Creating recursive procedures
      Using Recursion in your Access database
      Recursion Demystified: Creating Subfolders



8.   Feedback                                                                                                                                             Return To Top

     Please use the contact form below to let me know whether you found this article interesting/useful or if you have any questions/comments.

     Please also consider making a donation towards the costs of maintaining this website. Thank you



      Colin Riddington                     Mendip Data Systems                           Last Updated 29 Dec 2022



Return to Speed Test List Page 14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Return to Top