Number system convertion with Recursive function - Error in return value

Question

I have to make a program where I have to convert numbers from the decimal system into another one (base 2 to 9), like in my first question.

But this time I have to make it using a recursive function. So I came with:

function cambiarBase(n,b: integer): string;
Begin
if n < b then
  cambiarBase := inttostr(n)
else 
  cambiarBase := inttostr(n mod b) + cambiarBase(n div b, b);
End;

It takes 2 integer variables, 'n' being the decimal number and 'b' being the base, and returns a string with the converted number. At the button procedure I show the number in a TMemo

memo1.Lines.Add(cambiarBase(n,b)); 

The problem I have is: with the function the way it is gives the digits in the reverse order (e.g. 301 in base 9 is 364, but its shown as 463). But if I use a ReverseString function after the if statement then the number its shown in a different order (in the example, the number would be now 634).

But if I apply the ReverseString function at the memo1.Lines.Add (outside of the function) then it shows the correct convertion.

What I want is to know how can I make it return the correct order of the digits by the function itself.

The program compiles it without any errors.

Again, thanks for reading.

LeoAM

Answer 1

You just need to reverse the order of concatenation. Instead of:

cambiarBase := inttostr(n mod b) + cambiarBase(n div b, b);

you write

cambiarBase := cambiarBase(n div b, b) + inttostr(n mod b);

If you think about this it should be obvious that the concatenation should be this way round. In that expression, the inttostr(n mod b) term is the less significant term and so appears on the right.

For what it is worth, I think that this code reads much better if you use Result rather than the function name. Especially for a recursive function it can be hard visually to distinguish between the result variable and the recursive call. I'd write it like this:

function cambiarBase(n, b: Integer): string;
begin
  if n < b then
    // termination
    Result := IntToStr(n)
  else 
    // recursive step
    Result := cambiarBase(n div b, b) + IntToStr(n mod b);
end;

---

Let's work through a simple example for the sake of illustration. Let's say 27 base 4 which we know to be equal to 123 (16 + 2*4 + 3).

cambiarBase(27, 4) = cambiarBase(6, 4) + inttostr(3)

Next we need to evaluate

cambiarBase(6, 4) = cambiarBase(1, 4) + inttostr(2)

And finally the termination

cambiarBase(1, 4) = inttostr(1)

Plug it all together and you have

cambiarBase(27, 4) = inttostr(1) + inttostr(2) + inttostr(3)