How to keep track of the results while doing a recursion-CodePudding

I want to use recursion in converting a decimal number into octal. I have a problem in keeping track of the results of each recursion step and append them into a list or a string. I will appreciate your help.

def dectoOct(decimal):
    L = ''
    if decimal == 0:
        return 0
    if decimal > 0:
       L = str(decimal % 8)   L
       dectoOct(decimal//8)
    return L    
print(dectoOct(30))

CodePudding user response：

You just need to return the value as you go:

def dec_to_oct(n):
    if n == 0:
        return '0'
     
    left = n // 8
    if left:
        return dec_to_oct(n // 8)   str(n % 8)
    else:
        return str(n % 8)

# all are strings
foo(0)  # 0
foo(37) # 45
foo(40) # 50

CodePudding user response：

This is how I would do it, and whilst it is functional, it is probably not the best way to do it as global vars can be frowned upon, so I encourage other users to answer too.

I would use a global var to hold the results and in each case of a good result, append to that list.

Define the list outside your functions
Invoke it in your function with the global qualifier

Append to it when you get a result you want

  results = []

  def dectoOct(decimal):
      global results
      L = ''
      if decimal == 0:
          return 0
      if decimal > 0:
         L = str(decimal % 8)   L
         results.append(L)
         dectoOct(decimal//8)
      return L    
  print(dectoOct(30))

CodePudding user response：

I'm referring to Someone Else answer. Instead of using a global variable, you can include your variable in the arguments of the function like this:

def dectoOct(decimal, results = []):
    L = ''
    if decimal == 0:
        print(results)
        return 0
    if decimal > 0:
        L = str(decimal % 8)   L
        results.append(L)
        dectoOct(decimal//8)
    return L    
print(dectoOct(30))

of course if you need a print on each iteration just put print(results) in decimal > 0 case.

CodePudding user response：

As other answers show your code is perfectly salvageable, just L is not needed at all. However it may be worth pointing out how it could look a bit different.

Let's start with the stopping criteria. When converting to another base there are two cases:

The number in our hand can be represented as a single digit in the target base
The number in our hand needs multiple digits in the target base

In the first case we simply return the number converted to the new base, and as a string of course. In case of octal, it's str(x), in case of larger bases some indexing into a list/string could do the job (like "0123456789ABCDEFGH..."[x]).
Here we have octal, so

def dec_to_oct(n):
  if n < 8:
    return str(n)

This will work for n=0...7 (and will produce None above). So this one covers n == 0 too.
And in the other case comes the return dec_to_oct(n // 8) str(n % 8) shown already (and its parts also appear in your original code):

def dec_to_oct(n):
  if n < 8:
    return str(n)
  return dec_to_oct(n // 8)   str(n % 8)

print([dec_to_oct(n) for n in range(20)]

Displays

['0', '1', '2', '3', '4', '5', '6', '7', '10', '11', '12', '13', '14', '15', '16', '17', '20', '21', '22', '23']

There is the other "sub-species" of recursion, when you always get into the function and do nothing when meeting the exit criteria. The n == 0 check resembles that one, just it can't tell apart "real" 0 from "stop" 0. Otherwise it can work, but then it should return an empty string (here I return _ instead for better - well, actual - visibility):

def dec_to_oct(n):
  if n == 0:
    return '_'
  return dec_to_oct(n // 8)   str(n % 8)

print([dec_to_oct(n) for n in range(20)])

Now the recursion is unconditional, if we do anything at all, we recurse (and the return '_' counts as doing nothing). This almost works, except for dec_to_oct(0):

['_', '_1', '_2', '_3', '_4', '_5', '_6', '_7', '_10', '_11', '_12', '_13', '_14', '_15', '_16', '_17', '_20', '_21', '_22', '_23']

So this hit-the-wall kind of recursion can be simpler, just there may be edge cases. Like here the n == 0 case could be handled in an outer function, and do the recursion only in the other case:

def dec_to_oct(n):
  if n == 0:
    return '0'
  def inner(n):
    if n == 0:
      return '_'
    return inner(n // 8)   str(n % 8)
  return inner(n)

print([dec_to_oct(n) for n in range(20)])

This one produces

['0', '_1', '_2', '_3', '_4', '_5', '_6', '_7', '_10', '_11', '_12', '_13', '_14', '_15', '_16', '_17', '_20', '_21', '_22', '_23']