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
Cover image created with Microsoft Designer