Calculating Gift Counts for "The Twelve Days of Christmas": Recursion Edition

In Wednesday's article, I posted a reader challenge:

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

SPOILER ALERT: If you would like to try figuring it out on your own, follow the link above to read the original article before scrolling down to see one of my solutions.

The goal is to write a function that takes as input the first column (Day of Christmas) and returns as output the last column (Cumulative gifts):

Using Recursion to Calculate the Total

In general, recursion is harder for programmers to wrap their head around than non-recursive solutions (myself included).

In some situations, though, it maps more closely to how our brains naturally solve a problem.  The classic example is with any sort of hierarchical tree structure, such as Windows subfolders.  

It turns out that it also works well with pear tree structures, as we have here.

Explaining the Algorithm

The first part of the function is a loop that counts the number of gifts given on a single day.  

The next section of the function adds in the number of gifts given on the previous day.  It does this by calling itself but passing the previous day of Christmas.

The final section acts as a brake to terminate the recursion.  Once DayOfXmas = 1 (i.e., the first day of Christmas), the function returns a literal 1 rather than calling itself again.

'--== Recursive Version ==--
Function GiftsByXmasDay(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
        GiftsByXmasDay = GiftsThisDay + GiftsByXmasDay(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
        GiftsByXmasDay = 1
    End If
End Function

Referenced articles

Reader Challenge: Write a Formula to Calculate Gift Totals in “The Twelve Days of Christmas”

How many total gifts does one’s true love deliver by the nth day of Christmas? It’s a deceptively tricky problem to solve.

No Longer SetMike Wolfe

Cover image created with Microsoft Designer