The RESTRICTIONS ARE:

NO ITERATION OR LOOPS OR MAP OR LAMBDA.

NO MODULES ALLOWED TO BE IMPORTED EXCEPT MATH

ONLY RECURSION IS ALLOWED!

4 Spelling a Number You may use any form of recursion for this problem. Abstract list functions are prohibited. Write a function spell_number(n, group_names) that consumes a natural number n, and a list of strings group_names, and returns the English spelling of n as a string English numbers are spelled in groups of three digits. For instance, 123,456,789 is (123) million (456) thou- sand (789), with each parenthetical spelled as an independent three-digit number. In order for spell_number to handle arbitrarily large numbers, the names of each three-digit grouping (typically "", "thousand", "million", "billion", etc, but in reverse order) are provided as a list argument, group_names. The list group_names must therefore be at least as long as the number of digits in the number divided by three. Typically, the last group name will be "", as the last group has no name in English, but this is not a requirement of spell_number. We describe the algorithm for spelling a number in three steps: Full numbers, three-digit numbers, and one-digit numbers. The algorithm for spelling a full number n in English, with group names group_names, is as follows: If n is 0, "zero". Otherwise, - Convert n to a string s. - Add enough "O"s to the left of s to extend it to 3*len (group_names) digits. - Break s into groups of three digits. Convert each group g into a spelling: * If g is "000", then this group is not spelled, and should be ignored. * Otherwise, Use the algorithm for spelling a three-digit number, below, to spell g. Append " " + group_names[i], where i is the 0-indexed number of this group. Trim any excess spaces at the end of the string. - Join each spelled group's strings, with spaces in between, to produce the final string. The algorithm for spelling a three-digit number m in English is as follows: If the first digit of m is not 0, start with the string for that digit, concatenated to " hundred ". Otherwise, start with "". If the second digit of mis 1, then append a "-teen spelling", based on the third digit: "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", or "nineteen". If the second digit of m is not 1: - If the second digit of m is not 0, then append a tens spelling based on the second digit, which must be between 2 and 9: "twenty ", "thirty", "forty", "fifty", "sixty ", "seventy ", "eighty ", or "ninety ". - If the third digit of m is not 0, append the string for the third digit. Trim any excess spaces at the end of the string. The strings for a single digit are "one", "two", "three", "four", "five", "six", "seven", "eight", and "nine". HINTS: This algorithm is written in two parts because it will be useful to use (at least) those helper functions! In many parts of the algorithm, each number produces a different string. Think about how you can store the strings to make this conversion fast and easy. Different dialects of English use slightly different spellings of numbers, in particular whether "and" or hyphens should ever be included. Please follow the algorithm above, which includes neither "and" nor hyphens. Samples: spell_number(0, [""]) => "zero" spell number (42, [""]) => "forty two" spell_number (900, [""]) => "nine hundred" spell_number (42713, ["thousand", ""]) => "forty two thousand seven hundred thirteen" spell_number (4000000, ["million", "thousand", "units"]) => "four million" spell number (8000010, ["million", "thousand", ""]) => "eight million ten" spell_number (123456789, ["billion", "million", "thousand", ""]) => "one hundred twenty three million four hundred fifty six thousand seven hundred eighty nine" spell_number (2000124001,["billion","million","thousand","units"]) => "two billion one hundred twenty four thousand one units" 4 Spelling a Number You may use any form of recursion for this problem. Abstract list functions are prohibited. Write a function spell_number(n, group_names) that consumes a natural number n, and a list of strings group_names, and returns the English spelling of n as a string English numbers are spelled in groups of three digits. For instance, 123,456,789 is (123) million (456) thou- sand (789), with each parenthetical spelled as an independent three-digit number. In order for spell_number to handle arbitrarily large numbers, the names of each three-digit grouping (typically "", "thousand", "million", "billion", etc, but in reverse order) are provided as a list argument, group_names. The list group_names must therefore be at least as long as the number of digits in the number divided by three. Typically, the last group name will be "", as the last group has no name in English, but this is not a requirement of spell_number. We describe the algorithm for spelling a number in three steps: Full numbers, three-digit numbers, and one-digit numbers. The algorithm for spelling a full number n in English, with group names group_names, is as follows: If n is 0, "zero". Otherwise, - Convert n to a string s. - Add enough "O"s to the left of s to extend it to 3*len (group_names) digits. - Break s into groups of three digits. Convert each group g into a spelling: * If g is "000", then this group is not spelled, and should be ignored. * Otherwise, Use the algorithm for spelling a three-digit number, below, to spell g. Append " " + group_names[i], where i is the 0-indexed number of this group. Trim any excess spaces at the end of the string. - Join each spelled group's strings, with spaces in between, to produce the final string. The algorithm for spelling a three-digit number m in English is as follows: If the first digit of m is not 0, start with the string for that digit, concatenated to " hundred ". Otherwise, start with "". If the second digit of mis 1, then append a "-teen spelling", based on the third digit: "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", or "nineteen". If the second digit of m is not 1: - If the second digit of m is not 0, then append a tens spelling based on the second digit, which must be between 2 and 9: "twenty ", "thirty", "forty", "fifty", "sixty ", "seventy ", "eighty ", or "ninety ". - If the third digit of m is not 0, append the string for the third digit. Trim any excess spaces at the end of the string. The strings for a single digit are "one", "two", "three", "four", "five", "six", "seven", "eight", and "nine". HINTS: This algorithm is written in two parts because it will be useful to use (at least) those helper functions! In many parts of the algorithm, each number produces a different string. Think about how you can store the strings to make this conversion fast and easy. Different dialects of English use slightly different spellings of numbers, in particular whether "and" or hyphens should ever be included. Please follow the algorithm above, which includes neither "and" nor hyphens. Samples: spell_number(0, [""]) => "zero" spell number (42, [""]) => "forty two" spell_number (900, [""]) => "nine hundred" spell_number (42713, ["thousand", ""]) => "forty two thousand seven hundred thirteen" spell_number (4000000, ["million", "thousand", "units"]) => "four million" spell number (8000010, ["million", "thousand", ""]) => "eight million ten" spell_number (123456789, ["billion", "million", "thousand", ""]) => "one hundred twenty three million four hundred fifty six thousand seven hundred eighty nine" spell_number (2000124001,["billion","million","thousand","units"]) => "two billion one hundred twenty four thousand one units