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:

Write a recursive function that will take in an integer and return the Roman numeral associated with that integer. Assume the integers are not greated than 1000.

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

• 4000 is MMMM, not sure what 5000 is, so I can't subtract it for that case.
• Integers will be greater than 0
• Keep numbers as integers until reporting the final string of characters

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

I need to keep track of how many digits long each number is and the leading digit. Each of the digits and locations will tell me which Roman numeral to add to the string. As I add to the string, I'll move from the left to right sides of the input integer.

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?

I will be using strings and integers in this problem. The strings will be added onto recursively. I don't believe I will need any other data types at this time.

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

1. Make a function that takes in an integer as an argument.
2. Check if that integer is zero, if so, kick out of recursion.
3. Check if integer is 1000 or above, find out first digit and add that many M's to the string. Subtract the 1000s from the integer and make the subtracted integer the input to the function recursively.
4. Check if integer is 900 or above, add CM to string and subtract 900 from integer. Make subtracted integer the input to the function recursively.
5. Check if integer is 500 or above, add D to string and subtract 500 from integer. Make subtracted integer the input to the function recursively.
6. Check if integer is 100 or above, check leading digit, add that many C's to the string. Call function.
7. Repeat for rest of digits in a similar way to above.
8. String should be reported once step 2 triggers as true.

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

I would think the BigO notation for time complexity is O(n). This is because checking the size of a integer is relatively simple with a O(1), but then the function is called over and over again, making the function be called in proportion to n. I believe the space complexity is O(n).

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"

toRoman.js

function toRoman(num) {
  if(num === 0) {
    return ''
  } else if(num >= 1000) {
    let leadingDigit = Math.floor(num / 1000);
    let m = '';
    for(let i = leadingDigit; i > 0; i--){
      m += ('M');
    }
    return m + toRoman(num-leadingDigit*1000);
  } else if (num >= 900) {
    let cM = 'CM';
    return cM + toRoman(num-900);
  } else if (num >= 500) {
    return D + toRoman(num-500);
  } else if (num >= 100) {
    let leadingDigit = Math.floor(num / 100);
    let c = '';
    for(let i = leadingDigit; i > 0; i--){
      c += ('C');
    }
    return c + toRoman(num-leadingDigit*100);
  } else if (num >= 90) {
    let xC = 'XC';
    return xC + toRoman(num-90);
  } else if (num >= 50) {
    let l = 'L';
    return l + toRoman(num-50);
  } else if (num >= 40) {
    let xL = 'XL';
    return xL + toRoman(num - 40);
  } else if (num >= 10) {
    let leadingDigit = Math.floor(num / 10);
    let x = ''
    for(let i = leadingDigit; i > 0; i--){
      x += ('X');
    }
    return x + toRoman(num - leadingDigit*10);
  } else if (num === 9){
    return 'IX' + toRoman(0)
  } else if (num >= 5) {
    return 'V' + toRoman(num - 5);
  } else if (num === 4) {
    return 'IV' + toRoman(0);
  } else if (num > 0) {
    let i = 'I';
    for(j=num; j>0; j--){
      i += 'I'
    }
    return i + toRoman(0)
  }
}

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"