# Recursive function with strings and integers

You may use bitwise operators:

``````# Define the length of the code word in bits
# Normaly i would expect the encoding word
# length as a parameter of the function or as a member of a relating class.
word_length = 5

# Define the bitmask: 0000 0000  0000 0000  0000 0000  0000 0000  0001 1111
bitmask = 2 ** word_length - 1

def decompress(n):
result = ''
if n > 0:
# Take the only the last n bit by a and with the bitmask
letter_code = n & bitmask
# Decode the resulting code
result += alphabet[letter_code]
# recursively call the function without the current letter
# by using a bitwise right shift with the word length
result += aux(n >> word_length)
return result
``````

But if you have to use the division and modulo operators:

``````word_length = 5

max_letters_count = 2 ** word_length

def decompress(n):
result = ''
if n > 0:
# Take the only the last n bit by taking the modulo with the max_letters_count
letter_code = n % max_letters_count
# Decode the resulting code
result += alphabet[letter_code]
# recursively call the function without the current letter
# by using a integer division with the max_letters_count
result += aux(n // max_letters_count )
return result
``````

Now you can make these functions tail recursive (https://en.wikipedia.org/wiki/Tail_call):

``````def aux_tail_recursive(result_string, code):
if code <= 0:
return result_string
result_string += alphabet[code & bitmask]
next_code = code >> word_length
return aux_tail_recursive(result_string, next_code)
``````

or

``````def decompress_tail_recursive(result_string, code):
if code <= 0:
return result_string
result_string += alphabet[code % max_value]
code_next = code // max_value
return decompress_tail_recursive(result_string, code_next)
``````

CLICK HERE to find out more related problems solutions.

Scroll to Top