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:

Given a number, write a recursive function that converts the number to the most efficient Roman Numeral.

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

• The input will be greater than 0.
• Romans didn't have recursive functions

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

I have seen similar problems with converting monetery amounts to change. I think with recursion we will want to perform a subtraction each time we call the function. At a high level, our base case will be when our number is 0. Our recursive case will subtract a certain amount from the number and convert that amount into a Roman Numeral.

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 think an object will be used to hold the Roman Numerals. Maybe not...maybe if I'm using a conditional it would not be necessary. I'm envisioning a very long conditional that would probably work but seems very inefficient. I guess we have to store the Roman Numerals as well so maybe do that in an array that we can flatten or join to a string at the end.

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

* input: number
* output: string of Roman Numerals
* base case: when number equals 0
* recursive case: subtract from the Number and assign a Roman Numeral
* in recursive have if blocks for each Roman Numeral...for example (if num > 1000) {}
* inside these if blocks, subtract the amount from the number and also assign a variable 

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

I think BigO would be O(n) / linear because there is not a loop being used. I believe the callstack would suffer from the recursive function but BigO would still be linear. I think the space complexity would be 1 - 2x, one for the array and possibly one for an object. O(n) is for iterating over an array...which I feel this is doing but if not, I guess it would be O(1) / constant time since it is just doing a basic if/else and subtraction each time. As you can see...I'm not really sure how BigO works with recursion...

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"

roman_numeral_recursion_code.txt

// input: number
// output: string of Roman Numerals
// base case: when number equals 0
// recursive case: subtract from the Number and assign a Roman Numeral
// in recursive have if blocks for each Roman Numeral...for example (if num > 1000) {}
// inside these if blocks, subtract the amount from the number and also assign a variable 


function toRoman(num) {
    // create roman numeral variable
    let rn; 
    // base case
    if (num === 0) {
        return ''
    }
    // recursive case
    // if blocks!
    if (num >= 1000) {
        num -= 1000
        rn = 'M'
    } else if (num >= 900) {
        num -= 900
        rn = 'CM'
    } else if (num >= 500) {
        num -= 500
        rn = 'D'
    } else if (num >= 400) {
        num -= 400
        rn = 'CD'
    } else if (num >= 100) {
        num -= 100
        rn = 'C'
    } else if (num >= 90) {
        num -= 90
        rn = 'XC'
    } else if (num >= 50) {
        num -= 50
        rn = 'L'
    } else if (num >= 40) {
        num -= 40
        rn = 'XL'
    } else if (num >= 10) {
        num -= 10
        rn = 'X'
    } else if (num >= 9) {
        num -= 9
        rn = 'IX'
    } else if (num >= 5) {
        num -= 5
        rn = 'V'
    } else if (num >= 4) {
        num -= 4
        rn = 'IV'
    } else if (num >= 1) {
        num -= 1
        rn = 'I'
    }
    // return
    return rn + toRoman(num)
}
  
  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"