Python tail recursion optimization in this algo?

Question

I got the following problem: Let's consider the following encoding table:

0 -> A
1 -> B
2 -> C
...

input: string containing a list of integers
output: int representing the number of words that can be encoded from the input
examples:

"0" -> 1 (word is A)
"10" -> 2 (words are BA and K)
"121" -> 3 (words are BCB, MB and BV)

I wrote this algo

import string
sys.setrecursionlimit(100)  # limit the number of recursions to 100
# {0: 'a', 1: 'b', etc.}
dict_values = dict(zip(range(26), string.ascii_lowercase))

def count_split(list_numbers: list) -> int:
    if len(list_numbers) == 0:
        return 0

    elif len(list_numbers) == 1:
        return 1

    elif len(list_numbers) == 2:
        if int(list_numbers[0]) == 0:
            return 1

        elif 10 <= int("".join(list_numbers)) <= 25:
            return 2

        else:
            return 1

    else:  # list_numbers contains at least three elements
        if count_split(list_numbers[:2]) == 2:
            return count_split(list_numbers[1:]) + count_split(list_numbers[2:])

        else:
            return count_split(list_numbers[1:])

def get_nb_words(code: str) -> int:
    return count_split(list(code))

# print(get_nb_words("0124")) -> 3
# print(get_nb_words("124")) -> 3
# print(get_nb_words("368")) -> 1
# print(get_nb_words("322")) -> 2
# print(get_nb_words("12121212121212121212")) -> 10946

Surprisingly, this algo works on the last example "12121212121212121212". I expected the number of recursions to be exceeded because at each step, the function count_split is called twice on a list. Thus, the number of calls is much more than 100 (even more than 1000) !

In the meanwhile I found this post on stackoverflow saying that tail recursion is not optimized in Python, so I'm a bit suprised !

Could someone explain to me why the recursion limit is not exceed in this algorithm ?

It's a little late for me, but I think your maximum recursion *depth* (which is what matters) would only be about the length of the input string, no? Note, `recursionlimit` is a little misleading, it's actually the maximum depth of the call stack. — juanpa.arrivillaga, Nov 09 '20 at 12:23
yes, so I guess that recursion *depth* (which is set to 1000 by default) is not *the number of times the function is called* but *the number of inputs with which the function is called*. Am I getting this right ? — dallonsi, Nov 09 '20 at 12:30
No, it isn't the number of inputs with which the function is called. It's the maximum depth of the call stack, or is that what you meant? Again, sorry, it's late for me — juanpa.arrivillaga, Nov 09 '20 at 12:31
oh ok the depth of the tree representing the successive calls, right ? — dallonsi, Nov 09 '20 at 12:34
Well, the entirety of recursive calls can be seen as a tree if it is branching out, but yes, at any given moment it is just a stack. — tobias_k, Nov 09 '20 at 12:45

score 0 · Accepted Answer · edited Nov 09 '20 at 12:47

You care about the recursion depth, i.e. the maximum depth (height?) of the call stack.

Here's an empirical approach: (code that measures the depth)

import string, sys
sys.setrecursionlimit(100)  # limit the number of recursions to 100

dict_values = dict(zip(range(26), string.ascii_lowercase))
stack = []
max_depth = 0
def count_split(list_numbers: list) -> int:
    global max_depth
    stack.append(None)
    max_depth = max(max_depth, len(stack))
    if len(list_numbers) == 0:
        return 0

    elif len(list_numbers) == 1:
        return 1

    elif len(list_numbers) == 2:
        if int(list_numbers[0]) == 0:
            return 1

        elif 10 <= int("".join(list_numbers)) <= 25:
            return 2

        else:
            return 1

    else:  # list_numbers contains at least three elements
        if count_split(list_numbers[:2]) == 2:
            stack.pop()
            result = count_split(list_numbers[1:]) + count_split(list_numbers[2:])
            stack.pop(); stack.pop()
            return result

        else:
            result = count_split(list_numbers[1:])
            stack.pop()
            return result

def get_nb_words(code: str) -> int:
    return count_split(list(code))

print(get_nb_words("12121212121212121212"))
print(max_depth) # 20

Python tail recursion optimization in this algo?

1 Answers1