# 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
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

*Cover image created with Microsoft Designer*