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

In the second solution to my recent reader challenge, I use recursion to calculate the cumulative number of gifts given for each day of the "12 Days of Christmas."

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
Next NumberOfItems

If DayOfXmas > 1 Then
'Use recursion to call the function for each previous day
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