Splitting a string into chunks using recursion

Question

I am trying to split a string of arbitrary length into chunks of 3 characters. I know this question has been asked previously (How do you split a list into evenly sized chunks?), but that answer solves the problem with a list comprehension; I'm trying to solve the problem using a recursive function call, so my question is more about recursive functions calls in Python.

My function works fine until the "base case", the very last string of 3 or less characters. I am getting a TypeError: can only concatenate list (not "NoneType") to list.

Why is the base case returning None instead of a list? I explicitly create a list called final_value in the base case and return that. I even have a debugging print statement that shows me that the base case return value is of type <class 'list'>.

My code is below.

three_char_strings = []

def split3(str):
    if len(str) <= 3:
        final_value = []
        final_value.append(str)
        print('Final value: %s\nFinal value type: %s\n' % (final_value, type(final_value))) #For debugging
        return final_value
    else:
        beginning = str[0:3]
        three_char_strings.append(beginning)
        remaining = str[3:]
        three_char_strings + split3(remaining)

Your recursive function only actually `return`s in the base case - it needs to do it in both. — jonrsharpe, Feb 17 '15 at 15:58
Yes I see that now and I need to fix that. Thank you. But that still doesn't fix the problem of why the base case is returning a "NoneType". — LeonardShelby, Feb 17 '15 at 16:01
The base case isn't, **the other case is** (without an explicit `return` you get `None` back by default). — jonrsharpe, Feb 17 '15 at 16:01
You're right. I edited it and added a return statement in the recursive part. I no longer get any error. However, the final string from the base case is not being added to my list. For example, `splits3('abcdefghijklmnopqrstuvwxyz')` returns ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqr', 'stu', 'vwx']. The final string 'yz' is not being added to the list. — LeonardShelby, Feb 17 '15 at 16:04
Writing a recursive function that uses a global variable is a bad idea. Consider what happens if you call it twice. — interjay, Feb 17 '15 at 16:09

score 5 · Accepted Answer · edited May 23 '17 at 12:05

You have two problems:

You only return in the base case, so the other case will implicitly return None; and
You don't mutate three_char_strings in the base case. In fact, it's not clear why you would implement this to mutate an external list at all, as this will cause problems if you need to call it again.

You should probably have done something like:

def split3(str):
    if len(str) <= 3:
        return [str]
    else:
        beginning = str[:3]
        remaining = str[3:]
        return [beginning] + split3(remaining)

Which does what you want, without relying on the three_char_list list to be in-scope and empty when the function is called:

>>> split3('abcdefghijklmnopqrstuvwxyz')
['abc', 'def', 'ghi', 'jkl', 'mno', 'pqr', 'stu', 'vwx', 'yz']

The downside of that approach is that it creates several lists. If you want one list per top-level call, you could do e.g.:

def split3(str, out=None):
    if out is None:
        out = []
    out.append(str[:3])
    if len(str) > 3:
        split3(str[3:], out)
    return out

If you're wondering why out=None, see "Least Astonishment" and the Mutable Default Argument.

Thanks. I couldn't figure out how to do it without a global list. I just didn't know enough. Now I do. Thank you. — LeonardShelby, Feb 17 '15 at 16:20

score 2 · Answer 2 · answered Feb 17 '15 at 16:04

2

Though the original issue was that your non-base-case didn't have a return statement (meaning it implicitly returned None), it's also instructive to see how the code could be simplified in Python

def split3(s):
    return [s] if len(s) <= 3 else [s[:3]] + split3(s[3:])

answered Feb 17 '15 at 16:04

ely

74,674
34
147
228

Thanks Mr. F. This is the more elegant Pythonic solution of course, and I will use it in the future. I didn't check your response as "the answer" because I really wanted to get into the weeds of my recursive function. – LeonardShelby Feb 17 '15 at 16:21

Splitting a string into chunks using recursion

2 Answers2