How many gifts?

   

"The Twelve Days of Christmas" is a cumulative song, meaning that each verse is built on top of the previous verses. There are twelve verses, each describing a gift given by "my true love" on one of the twelve days of Christmas.

The first three verses run, in full, as follows:

On the first day of Christmas my true love sent to me

A partridge in a pear tree. ( Note - So 1 gift was given)

On the second day of Christmas my true love sent to me

Two turtle doves

And a partridge in a pear tree. (So 2 + 1 gifts were given)

On the third day of Christmas my true love sent to me

Three French hens,[5]

Two turtle doves,

And a partridge in a pear tree. (So?)

Subsequent verses follow the same pattern, each adding one new gift and repeating all the earlier gifts so that each verse is one line longer than its predecessor:

? 4 calling birds

? 5 gold rings

? 6 geese a-laying

? 7 swans a-swimming

? 8 maids a-milking

? 9 ladies dancing

? 10 lords a-leaping

? 11 pipers piping

? 12 drummers drumming

Please create an algorithm that outputs the total number of gifts given on each day. Express your algorithm in the following 3 ways:

1. Summation using sigma notation
2. Pseudo-code
3. Program in C++ or Python

Express the time complexity of your algorithm in Big-O notation

For the pseudo code style, using this module

Make sure your program:

• Compiles and runs without hanging or errors
• Is commented in a professional manner

40 2. 3. If you find a box, go to step 1. If you find a key, you're done! Chapter 3 | Recursion Which approach seems easier to you? The first approach uses a while loop. While the pile isn't empty, grab a box and look through it: def look_for_key (main_box): pile = main_box.make_a_pile_to_look_through () while pile is not empty: box for item in box: if item.is_a_box(): pile.grab_a_box() pile.append (item) elif item.is_a_key(): print "found the key!" The second way uses recursion. Recursion is where a function calls itself. Here's the second way in pseudocode: def look_for_key (box): for item in box: if item.is_a_box(): look for key (item) elif item.is_a_key(): print "found the key!" Recursion! Both approaches accomplish the same thing, but the second approach is clearer to me. Recursion is used when it makes the solution clearer. There's no performance benefit to using recursion; in fact, loops are sometimes better for performance. I like this quote by Leigh Caldwell