""" 
 baseConvert.py

 problem 5, chapter 13 from Zelle's book
 use recursion to write a baseConversion(num, base)
 routine which outputs the digits of the given number
 in that base.

  $ python baseConvert.py
 
  Finding num=25, base=2 ... 
    DEBUG: num=25, base=2, answerSoFar=[]
    DEBUG: num=12, base=2, answerSoFar=[1]
    DEBUG: num=6, base=2, answerSoFar=[0, 1]
    DEBUG: num=3, base=2, answerSoFar=[0, 0, 1]
    DEBUG: num=1, base=2, answerSoFar=[1, 0, 0, 1]
    DEBUG: num=0, base=2, answerSoFar=[1, 1, 0, 0, 1]
  answer is  [1, 1, 0, 0, 1]

  Finding num=25, base=8 ... 
    DEBUG: num=25, base=8, answerSoFar=[]
    DEBUG: num=3, base=8, answerSoFar=[1]
    DEBUG: num=0, base=8, answerSoFar=[3, 1]
  answer is  [3, 1]

"""

def baseConversion(num, base, answerSoFar=[]):
    """ Return [a,b,c] such that
        c + b**base + a*base**2 = num
    """
    print "  DEBUG: num={}, base={}, answerSoFar={}".format(
        num, base, answerSoFar)
    if num == 0:
        return answerSoFar
    else:
        return baseConversion(num/base,
                              base, 
                              [num % base] + answerSoFar)

print "Finding num=25, base=2 ... "
answer = baseConversion(25, 2)
print "answer is ", answer
print

print "Finding num=25, base=8 ... "
answer = baseConversion(25, 8)
print "answer is ", answer