Do it in Python 3.0 ONLY USE RECURSION, NO LOOPS

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 "0"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 spellg. Append u group_names[i], where i is the O-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 tvo" 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","] => Weight 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" spell number (5555, ["flibberty", "floppity"]) => "five flibberty five hundred fifty five floppity" 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 "0"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 spellg. Append u group_names[i], where i is the O-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 tvo" 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","] => Weight 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" spell number (5555, ["flibberty", "floppity"]) => "five flibberty five hundred fifty five floppity