Recursive Base Conversion Without Strings Or Arrays

A first semester Computer Science student who I am tutoring came to me with this problem and I am having great difficulty figuring it out, given the constraints of the assignment. Here it is:

Write a recursive C++ function of the form

int base_conv(unsigned short n,short r);

that accepts an integer n and converts it to base r, where r is an integer have the value 2,3,4,5,6,7,8, or 9.

The function must be recursive, and cannot use arrays, string, strings streams or any non standard functions. The solution must also be composed of C++ code comparable to what a first semester programming student would know.

>> hint: this algorithm work only when the result can store in an int variable;

Good code, zaghaghi, but better take a 64-bit integer, e. g. 1024 == 10 000 000 000 (base 2) > 32 bit. (For VC6 you also have to provide ostream operator).

Regards, Alex

#include <iostream>
using namespace std;

#ifndef _WIN32
#define HUGE long long
// **** remove that part below on UNIX ****
#else
#define HUGE __int64
#ifdef _MSC_VER
#if _MSC_VER <= 1200
std::ostream& operator<<(std::ostream& os, HUGE i )
{
char buf[20];
sprintf(buf,"%I64d", i );
os << buf;
return os;
}
#endif // _MSC_VER <= 1200
#endif // _MSC_VER
// **** remove that part above on UNIX ****
#endif // _WIN32

HUGE base_conv(unsigned short n,short r)
{
if(n<r)
return n;
HUGE result = base_conv(n/r, r);
result *= 10;
result += n%r;
return result;
}

int main(int argc, char *argv[])
{
while (true)
{
unsigned short n;
cout << "Enter number ==>";
cin >> n;
if (n == 0)
break;
cout << "Enter base ==>";
short r;
cin >> r;
if (r <= 0 || r >= 10)
break;
HUGE h = base_conv(n, r);
cout << n << " -> " << h << " (base=" << r << ")" << endl;

If you really are a tutor then this should be no problem to you. I have removed comments and used slightly cryptic variable names in the hope that this is not YOUR homework but this works in all bases up to base 16. It can be extended to any base just by extending the string.

// Number to string. n = number, s = string, d = digits, b = base.
// Do not pass an 'l' parameter.
void ntos ( int n, char * s, int d, int b, int l = 0 )
{
if ( l < d - 1 ) ntos ( n / b, s, d, b, l + 1 );
s[d-l-1] = "0123456789abcdef"[n % b];
}

// Call my conversion.
char s [10];
ntos ( 12345, s, 3, 10 );

Paul

0

SchmeelDealAuthor Commented:

zaghaghi, your solution was first and the most basic, thus you get the points.

itsmeandnobodyelse, although it was good, your solution had a bunch of extra stuff that I did not need.

PaulCaswell, yours is very similiar to what I came up with, it is beyond the scope of first semester student. I could explain that function to him, but he will only get credit for what has been taught in class to date.

0

Featured Post

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

int base_conv(unsigned short n,short r)

{

if(n<r)

return n;

int result = base_conv(n/r, r);

result *= 10;

result += n%r;

return result;

}

have a good programming day;