**Assignment:**

**Recursion**** Challenges**

**Reminder: Recursion**

the idea that something will re-occur in smaller amounts

divides a complex problem into smaller sub-problems (i.e. divide and conquer)

subproblems are smaller instances of the same type of problem.

is somehow self-referential (calls itself)

**For any of the challenges below, the solution must be a recursive algorithm. Much like merge sort, the main function might not be the recursive one - you might use a helper function.**

**Challenge #1 - The nth Day of Christmas:**

I'm sure you've heard the song - "On the first day of Christmas, my true love gave to meeeee...." By the time the song is done, at the end of the 12 days, my true love gave to me in total 364 items! Create the function xmasItems(n) where, given n days as an argument, it returns the total amount of items received throughout those days as an integer.

This task *must be done recursively*. **Hint:** this task does *not* utilize divide & conquer (since there is no array).

**Examples:**

xmasItems(12) ➞ 364

xmasItems(3) ➞ 10

xmasItems(31) ➞ 5456

**Challenge #****2 (two parts)**** - ****Decimal <> Binary Conversion****:**

**2A Return a Decimal Number**

Given a * string *of 0's and 1's that represents a binary value, return a

**number**which represents that number in

*decimal*

**.*** *bin_to_dec(bin)

Assuming correct & valid input.

**Examples:**

bin_to_dec("101010101") ➞ 341

bin_to_dec("111000111000111") ➞ 29127

bin_to_dec("10") ➞ 2

bin_to_dec("100000000000000000001") ➞ 1048577

bin_to_dec("1") ➞ 1

**2****B Return a Binary String**

Given a positive natural * number *in

*decimal*, return a

**string**which represents that number in

*binary*.

dec_to_bin(dec)

Assuming correct & valid input.

**Examples:**

dec_to_bin(1048576) ➞ "100000000000000000000"

dec_to_bin(263) ➞ "100000111"

dec_to_bin(255) ➞ "11111111"

dec_to_bin(17) ➞ "10001"

dec_to_bin(1) ➞ "1"

**Notes:**

These two functions *must be done recursively*. You are not permitted to use built-in conversion functions. You *are* permitted to use String functions like substring(), etc.

**Hint:** this task does *not* utilize divide & conquer (since there is no array). Also, it is important to remember some math skills:

*modulo*returns the*remainder*of a division. For example, 5 % 2 == 1Our number system (decimal) is

*base 10*which means each location is a power of 10. For example, 23 is 2*10^1 + 3*10^0 = 20 + 3Binary is

*base 2*which means each location is a power 2. For example, 101 = 1*2^2 + 0*2^1 + 1*2^0 = 4 + 1

**Challenge #****3**** - ****Min/Max****:**

Given an integer array (arr), find the minimum and maximum element present in it by making minimum comparisons **by using the divide-and-conquer technique**.

Your function will return a two-element array that contains [min, max]

This task *must be done recursively*.

**Examples:**

minmax([7, 2, 9, 3, 1, 6, 7, 8, 4]) ➞ [1, 9]

minmax([8, 3]) ➞ [3, 8]

minmax([1,2,0,4,5,0,5,6,0]) ➞ [0, 6]