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

2B 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 == 1

  • Our 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 + 3

  • Binary 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]