Recursive method to display the representation of an integer in a base

Question

Write a recursive method base() which accepts a non-negative integer n and a positive whole 1 < b < 10 and present the basic representation b of the whole n.

>>> base(0, 2)
0
>>> base(1, 2)
1
>>> base(10, 2)
1010
>>> base(10, 3) 
1 0 1

I just managed to make a non-recurring solution:

def base(n,b):
    restos = []
    quo = b+1
    if 1 < b <10:
        if n >=b:
            while quo >= b:
                resto = n % b
                quo = n // b
                n = quo
                restos.append(resto)
            return quo, restos[::-1]

print(base(72,2))

How to make the solution recursive in Python?

Answer 1

def conv(num,b):
    convStr = "0123456789abcdefghijklmnopqrstuvwxyz"
    if num<b:
        return convStr[num]
    else:
        return conv(num//b,b) + convStr[num%b]
print (conv(4,2)) #will just return 100

Answer 2

To convert to base 10, you could do so:

def base(n, b):
    if n == 0 or b == 10:
        return n

    return (n % b) + 10 * base(n // b, b)

If the number is zero or the basis is 10, there is no account to do, then return the number itself.

Otherwise, take the rest of the division of the number by the base (n % b) and add with 10 multiplied by the conversion of the number divided by the base. Confusing? Let’s see an example:

• Convert 3 to base 2: base(3, 2)
  • 3 is not equal to zero and the base is 2, does not enter the if
  • returns 3 % 2 (that is to say, 1) added with 10 * base(3 // 2, 2)
  • base(3 // 2, 2) is the same as base(1, 2)
    • 1 is not equal to zero and the base is 2, does not enter the if
    • returns 1 % 2 (that is to say, 1) added with 10 * base(1 // 2, 2)
    • base(1 // 2, 2) is the same as base(0, 2)
      • as n is zero, get in the if and returns the number itself (in this case, zero)
    • 10 * base(1 // 2, 2) is 10 * 0, resulting in zero. Added with 1 % 2, gives 1
  • 10 * base(3 // 2, 2) is 10 * 1, which is equal to 10. Added with 3 % 2, results in 11
• the function returns 11, which is the representation of 3 in base 2.

Obs: Just remembering that in fact the value returned is the number 11 itself (eleven) and it is in base 10. What we did was generate a base 10 value whose digits are the same as the original number (in this case, 3) was at base 2. So there’s no point in using this 11 thinking that its value will be 3.

---

For bases bigger than 10, there is no way to do only with these accounts, because some symbols used become letters. In this case you would have to use a predefined list of symbols and concatenate the strings (instead of summing and multiplying to construct the number), as was done in another answer (which accepts up to base 36).

In the background, the other answer uses the same logic, the difference is that it concatenates strings, adding new digits at the end, while the above solution multiplies by 10 to "push" the digits to the left.