Last Updated on August 17, 2021 by Hammad Rauf

Here is a retake on an old My-Old-Post. This time it is done using a recursive function. To allow arbitrarily long numbers in input (at most 64 bit long) a marker “X” is used instead of the word “million” or so on. A table lookup or hash function may be used (in a later version) to replace “X” with the “million” or other words.

Recursive Functions

A recursive function or the recursion technique is when a method or function calls itself with simpler arguments. The simpler arguments to a function can return a trivial (non-recursive) solution or end up in another recursive call. Eventually a properly designed recursive function will return a trivial result. Once it returns the trivial result, back-tracking can start which is handled by the compiler using system stack. C++, Java, Pascal and many other high level programming languages support Recursive Functions. In the code below “NumberToWord::convert(int64_t numb);” function is a recursive function.

Performance Overhead

There is a slight performance overhead when using a recursive function as compiler has to place the local variables and arguments in a stack frame, from where that data will be popped when backtracking. For slightly more efficient code, if a non recursive solution does not exist for a problem than a recursive function may be converted into non-recursive code using programming tools like linked lists (LIFO) or stack. But such solutions tend to appear more complicated and loose the simplicity of a recursive solution. The complexity is introduced when back-tracking has to be manually implemented.

Listing

You can try the code in the online C++ ISO compiler here , here-2 or here-3. Also the code is given below.

#include <sstream>
#include <iostream>
#include <stdio.h>
#include <sys/types.h>
#include <list>
#include <string>


class WinNumberToWordR {

public:
	std::string convert(uint64_t numb, int depth);

private:
	std::string convertInner(uint64_t numb);
	std::string matcher(int digit, int placeValue);
	std::string matchXtoWords(std::string xs);
};


std::string WinNumberToWordR::convert(uint64_t numb, int depth) {
	std::string words = "", words2 = "";
	std::string part_words = "";
	std::string part_xx = "", part_xword = "";
	uint64_t part_bigger = 0;
	uint64_t small_part = 0;
	int last3 = 0;

	if (numb < 1000) {
		words = convertInner(numb);
	}
	else {
		part_bigger = numb / 1000;
		small_part = numb - (part_bigger * 1000);
		part_words = convert(part_bigger, depth + 1);

		if (part_bigger > 1000) {
                        std::ostringstream ss;
			std::string  st = "";
			//st = std::to_string(part_bigger);
                        ss << part_bigger;
                        st = ss.str();
			std::string se = st.substr(st.length() - 3);
			//last3 = std::stoi(se);
                        std::istringstream is(se);
                        is>>last3;
		}
		else
			last3 = (int) part_bigger;
		if (last3 > 0)
			part_words += " ";
		part_xx = "";
		do {
			part_xx += "X";
			depth--;
		} while (depth >= 0);
		part_xword = matchXtoWords(part_xx);
		if (last3 > 0) {
			part_words += part_xword;
			part_words += " ";
		}

		words2 = convertInner(small_part);
		words = part_words + words2;
	}
	return words;
}

std::string WinNumberToWordR::convertInner(uint64_t numb) {
	std::string words = "";
	std::string wordTen = "";
	int hundred = 0;
	int tens = 0;
	int units = 0;
	bool teens = false;

	if ((numb < 1000) & (numb > 0)) {
		hundred = numb / 100;
		numb -= (hundred * 100);
		tens = numb / 10;
		numb -= (tens * 10);
		units = numb;
	}

	words += matcher(hundred, 100);
	if (hundred != 0)
		words += " hundred";
	wordTen += matcher(tens, 10);
	if ((wordTen.compare("ten") == 0) && (units > 0)) {
		teens = true;
		switch (units) {
		case 1: wordTen = "eleven"; break;
		case 2: wordTen = "twelve"; break;
		case 3: wordTen = "thirteen"; break;
		case 4: wordTen = "fourteen"; break;
		case 5: wordTen = "fifteen"; break;
		case 6: wordTen = "sixteen"; break;
		case 7: wordTen = "seventeen"; break;
		case 8: wordTen = "eighteen"; break;
		case 9: wordTen = "nineteen"; break;
		case 0: break;
		}
	}
	if ((hundred !=0) && ((tens!=0) || (units !=0)) )
		words += " ";
	words += wordTen;
    if ((!teens) && (hundred != 0) && (tens != 0) && (units !=0))
		words += " ";
	if (!teens)
		words += matcher(units, 1);

	return words;
}

std::string WinNumberToWordR::matcher(int digit, int placeValue) {
	std::string result = "";

	if ((placeValue == 1) | (placeValue == 100)) {
		switch (digit) {
		case 1: result = "one"; break;
		case 2: result = "two"; break;
		case 3: result = "three"; break;
		case 4: result = "four"; break;
		case 5: result = "five"; break;
		case 6: result = "six"; break;
		case 7: result = "seven"; break;
		case 8: result = "eight"; break;
		case 9: result = "nine"; break;
		case 0: result = "";
		}
	}

	if (placeValue == 10) {
		switch (digit) {
		case 1: result = "ten"; break;
		case 2: result = "twenty"; break;
		case 3: result = "thirty"; break;
		case 4: result = "forty"; break;
		case 5: result = "fifty"; break;
		case 6: result = "sixty"; break;
		case 7: result = "seventy"; break;
		case 8: result = "eighty"; break;
		case 9: result = "ninety"; break;
		case 0: result = "";
		}
	}

	return result;
}

std::string WinNumberToWordR::matchXtoWords(std::string xs) {
	std::string result = "";

	if (xs.compare("X") == 0)
		result = "thousand";
	else if (xs.compare("XX") == 0)
		result = "million";
	else if (xs.compare("XXX") == 0)
		result = "billion";
	else if (xs.compare("XXXX") == 0)
		result = "trillion";
	else if (xs.compare("XXXXX") == 0)
		result = "quadrillion";
	else if (xs.compare("XXXXXX") == 0)
		result = "quintillion";
	else if (xs.compare("XXXXXXX") == 0)
		result = "sextillion";
	else if (xs.compare("XXXXXXXX") == 0)
		result = "septillion";
	else if (xs.compare("XXXXXXXXX") == 0)
		result = "octillion";
	else if (xs.compare("XXXXXXXXXX") == 0)
		result = "nonillion";
	else if (xs.compare("XXXXXXXXXXX") == 0)
		result = "decillion";
	else if (xs.compare("XXXXXXXXXXXX") == 0)
		result = "undecillion";
	else if (xs.compare("XXXXXXXXXXXXX") == 0)
		result = "duodecillion";
	else result = xs;

	return result;
}

int main(int argc, char *argv[])
{
	uint64_t n = ((uint64_t)2147483647) << 30;
	//int64_t n=2147483647;
        //int n=98427543;
	//int n=900;
	printf("Hello World!\n");
        cout << "Number to Convert: " << n << endl;
        WinNumberToWordR n1;
        cout << "Converted result: " << (n1.convert(n, 0)) << endl;
	getchar();
	return 0;
}

Further Reading

• Recursion, http://www.cs.utah.edu/~germain/PPS/Topics/recursion.html Date accessed: October 26, 2016
• Stack, https://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Mips/stack.html Date accessed: October 26, 2016
• Stacks and Queues, http://pages.cs.wisc.edu/~vernon/cs367/notes/5.STACKS-AND-QUEUES.html Date accessed: October 26, 2016
• Back-tracking, https://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html Date accessed: October 26, 2016
• Large and Small Numbers, http://www.statman.info/conversions/number_scales.html Date accessed: December 11, 2019
• Prillionare, https://faculty.math.illinois.edu/~castelln/prillion_revised_10-05.pdf Date accessed: December 11, 2019