Decimal To Base Conversion Recursive and Iterative

Problem

Number System conversion is a famous Mathematical question that we encounter quite often being programmers. The problem states that given a natural decimal number, convert it to a given base from 2 to 36. There are three famous number systems, Binary base 2, Octal base 8, and Hexadecimal base 16. We can adopt these standard conversions and extend them to other base numbers from 2-36.

Video Tutorial – Number Conversion from Decimal to Base (2-36)

Iterative Algorithm

Declare a String variable called result to store the converted number.
Initialize the result to an empty String.
Loop till the number is greater than zero.
Use the Modulus operator to extract the digit using base.
Divide the number n by base.
Insert the extracted digit into the front of the result variable.
Repeat until the number is not zero.
The value stored in the result variable will be the conversion of a decimal number to the given base.

Recursive Algorithm

Base case: Return an empty string if the input number n is zero.
Recursive Step: Extract the digit by using the Modulus operator by base.
Divide the number n by base.
Convert the digit to a string
Return the Function with new n and concatenation of string created from the digit in step 4.
Once the recursive calls are complete, the function will return the conversion of the decimal number to the given base number.

Example

65535 Converted to Base 2 = 1111111111111111
65535 Converted to Base 3 = 10022220020
65535 Converted to Base 4 = 33333333
65535 Converted to Base 5 = 4044120
65535 Converted to Base 6 = 1223223
65535 Converted to Base 7 = 362031
65535 Converted to Base 8 = 177777
65535 Converted to Base 9 = 108806
65535 Converted to Base 10 = 65535
65535 Converted to Base 11 = 45268
65535 Converted to Base 12 = 31B13
65535 Converted to Base 13 = 23AA2
65535 Converted to Base 14 = 19C51
65535 Converted to Base 15 = 14640
65535 Converted to Base 16 = FFFF
65535 Converted to Base 17 = D5D0
65535 Converted to Base 18 = B44F
65535 Converted to Base 19 = 9AA4
65535 Converted to Base 20 = 83GF
65535 Converted to Base 21 = 71CF
65535 Converted to Base 22 = 638J
65535 Converted to Base 23 = 58K8
65535 Converted to Base 24 = 4HIF
65535 Converted to Base 25 = 44LA
65535 Converted to Base 26 = 3IOF
65535 Converted to Base 27 = 38O6
65535 Converted to Base 28 = 2RGF
65535 Converted to Base 29 = 2JQO
65535 Converted to Base 30 = 2COF
65535 Converted to Base 31 = 2661
65535 Converted to Base 32 = 1VVV
65535 Converted to Base 33 = 1R5U
65535 Converted to Base 34 = 1MNH
65535 Converted to Base 35 = 1IHF
65535 Converted to Base 36 = 1EKF

Code

main.cpp

/************************************************************
* Problem: Number Conversion: Decimal to Base 2-36
*
* Programmer: CodingHelpLine
* Website: https://codinghelpline.org
*
* Description:
*
* Number conversion is a Mathematical problem. It used to
* convert a natural number to any base between 2-36.
*
* Binary base 2
* Octal base 8
* Hexadecimal base 16
*
* The program writes two methods:
*
* 1. Iterative Solution
* 2. Recursive Solution.
*
* Example:
*
* 65535 -> in Base 2 or Binary = 1111111111111111
* 65535 -> in Base 8 or Octal = 177777
* 65535 -> in Base 16 or Hexadecimal = FFFF
*
************************************************************/
#include <iostream>
#include <string>

using std::string;
using std::cout;
using std::endl;

// Define Alpha
const string ALPHA = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

// Function Prototypes

/**
* Convert natural number to base between 2-36
*
* Iterative algorithm
* @return converted number as string
*/
string toBaseIterative(int n, int base);

/**
* Convert natural number to base between 2-36
*
* Recursive algorithm
* @return converted number as string
*/
string toBaseRecursive(int n, int base);

// Main Method - Entry point of program.
int main() {

int n = 65535;

// iterative
cout << "Iterative Call: " << endl;
cout << n << " in Base 2 Binary: " << toBaseIterative(n, 2) << endl;
cout << n << " in Base 8 Octal: " << toBaseIterative(n, 8) << endl;
cout << n << " in Base 16 Hexadecimal: " << toBaseIterative(n, 16) << endl;

cout << endl;
cout << "Recursive Call: " << endl;
cout << n << " in Base 2 Binary: " << toBaseRecursive(n, 2) << endl;
cout << n << " in Base 8 Octal: " << toBaseRecursive(n, 8) << endl;
cout << n << " in Base 16 Hexadecimal: " << toBaseRecursive(n, 16) << endl;

// Base 2 to 36
cout << endl;
cout << "65535 in Base 2-36" << endl;
for(int base = 2; base <= 36; base++)
{
cout << n << " in Base " << base << " = " << toBaseIterative(n, base) << endl;
}

return EXIT_SUCCESS;
}

/**
* Convert natural number to base between 2-36
*
* Iterative algorithm
* @return converted number as string
*/
string toBaseIterative(int n, int base)
{
// Declare and initialize result variable to empty string
string result = "";

while(n > 0)
{
// Extract digit from n
int digit = n % base; // work for any base for example 2-36
n = n / base; // remove the extracted digit

result.insert(result.begin(), 1, ALPHA[digit]);
}

return result; /// will be our result converted number
}

/**
* Convert natural number to base between 2-36
*
* Recursive algorithm
* @return converted number as string
*/
string toBaseRecursive(int n, int base)
{
// Base case
if(n == 0) {
return "";
}

// Recursive step
int digit = n % base; // extract digit
n = n / base; // remove the digit from n

return toBaseRecursive(n, base) + string(1, ALPHA[digit]);
}