roman_numeral_recursion.md

Instructions

1. Fork this gist, then "edit" the gist
2. Fill out the questions below
3. Click the "Add file" button and add your source code to the gist
4. Submit by the due time as instructed in Zoom

Do not publish your code on a public repl.it or repo or other public means.

Prompt

Write a recursive function that converts an integer into a string such that the number is represented in Roman Numerals in the most efficient way. eg, the number 4 could be written as 'IIII' but it's more efficient to use 'IV' since that's a shorter string Assume no number is greater than 4,000 Here are the Roman Numeral equivalents you'll need to know:

• M=1000
• CM=900
• D=500
• CD=400
• C=100
• XC=90
• L=50
• XL=40
• X=10
• IX=9
• V=5
• IV=4
• I=1

Rewrite the question in your own words:

• Taking in an integer, a function should return that number back as a string that represents the roman numeral verison of the number.

What assumptions will you make about this problem if you cannot ask any more clarifying questions? What are your reasons for making those assumptions?

• That recursion needs to be used? I don't think I'm understanding enough about roman numerals and would need to do more search/ask questions regarding that.
• Had to spend some time researching how to convert to roman numerals - used this source.

What are your initial thoughts about this problem? (high level design, 2-3 sentences)

Notes from before researching roman numeral conversion:

• Initially I thought I'd want to split the input, i.e. if it's 121 split into [1, 2, 1], and then check each value, but I don't think that's the right way to go since 1 as a roman numeral is I but in this case, that 1 represents a hundred, so would be C.
• I guess if I need to use recursion, there needs to be a base case to terminate the function. This isn't as apparent to me as the examples we went over in class, but I guess if I go the route of the array, once all numbers in the array have been converted to roman numerals, then exit and return the result? The recursive case would possible be the conversion of that index to roman numeral? Notes from after researching roman numeral conversion:
• After being very confused about how to approach this problem, I did some research on how to convert to roman numerals. I no longer will be spliting the input into an array as I instead want to take the number (i.e. 121) and compare it against the roman numeral equivalents list to find which number on the equivalent list the number is closest to, but still great than or equal to (in this case, 100). Then I'll return C and subtract that value from the number (121 - 100) and call the function again using the remaining number (this time through, it will be 21). This will be my recursive case, and the base case will be the remaining number is less than 1 since there is no roman numeral representation for numbers less than 1.

How would you identify the elements of this problem?

• Searching of Data
• Sorting of Data
• Pattern Recognition
• Build/Navigate a Grid
• Math
• Language API knowledge
• Optimization

Which data structure(s) do you think you'll use? What pros/cons do you see with that choice?

Notes from before researching roman numeral conversion:

• Maybe arrays since I can keep track of each value and it's place? I'm still not very confident on my initial approach idea and am not sure what other data structure would be useful in this case. Notes from after researching roman numeral conversion:
• I think I need to take the "Roman Numeral equivalents you'll need to know" and turn it into an object.

Write out a few lines of initial pseudocode: (mid-level design, this should be short, and not be real code!)

// setup object for roman numeral equivalents
// enter function toRoman(num)
// setup base case - if num is less than 1 - exit
// setup recursive case
// figure out way to loop through the roman numeral object (keys?)
// if num is greater than or equal to the value of the roman numeral we are iterating on...
// return that roman numeral key 
// AND
// call the toRoman function again with an argument that is num - the value of that roman numeral 

What do you think the Big O complexity of your algorithm is? (time complexity and space complexity)

JS Starter Code

function toRoman(num) {
  // your code goes here
}

console.log(toRoman(128));  // should return "CXXVIII"
console.log(toRoman(2000)); // should return "MM"
console.log(toRoman(2017)); // should return "MMXVII"
console.log(toRoman(1999)); // should return "MCMXCIX"

Ruby Starter Code

def to_roman(num)
  # your code goes here
end

puts to_roman(128)   # should return "CXXVIII"
puts to_roman(2000)  # should return "MM"
puts to_roman(2017)  # should return "MMXVII"
puts to_roman(1999)  # should return "MCMXCIX"