3

I've just run into a tricky issue. The following code is supposed to split words into chunks of length numOfChar. The function calls itself, which makes it impossible to have the resulting list (res) inside the function. But if I keep it outside as a global variable, then every subsequent call of the function with different input values leads to a wrong result because res doesn't get cleared.

Can anyone help me out?

Here's the code (in case you are interested, this is problem 7-23 from PySchools.com):

res = []

def splitWord(word, numOfChar):        
    if len(word) > 0:
        res.append(word[:numOfChar])
        splitWord(word[numOfChar:], numOfChar)    
    return res

print splitWord('google', 2)
print splitWord('google', 3)
print splitWord('apple', 1)
print splitWord('apple', 4)
Improve this question

3 Answers 3

Reset to default
5

A pure recursive function should not modify the global state, this counts as a side effect.

Instead of appending-and-recursion, try this:

def splitWord(word, numOfChar): 
    if len(word) > 0:
        return [word[:numOfChar]] + splitWord(word[numOfChar:], numOfChar)
    else:
        return []

Here, you chop the word into pieces one piece at a time, on every call while going down, and then rebuild the pieces into a list while going up.

This is a common pattern called tail recursion.

P.S. As @e-satis notes, recursion is not an efficient way to do this in Python. See also @e-satis's answer for a more elaborate example of tail recursion, along with a more Pythonic way to solve the problem using generators.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

@coltonpagefault: Please note that, while this is a good way to do it recursively, and efficient in a lot of languages such as LISP and Erlang, it is not in Python. So, it's good you use this example to learn recursion, but you don't want to use it in a production code. In real Python life, you probably would use a generator. I'll +1 because it's the right answer to the question.
Thanks for the feedback! I'll look at the code again tomorrow morning. It's been a long day here... @e-satis: By "generators" you're referring to the yield command, don't you?
Yes, I added an answer to elaborate on that matter.
2

Recursion is completely unnecessary here:

def splitWord(word, numOfChar):
   return [word[i:i+numOfChar] for i in xrange(0, len(word), numOfChar)]

If you insist on a recursive solution, it is a good idea to avoid global variables (they make it really tricky to reason about what's going on). Here is one way to do it:

def splitWord(word, numOfChar):
   if len(word) > 0:
      return [word[:numOfChar]] + splitWord(word[numOfChar:], numOfChar)
   else:
      return []
Improve this answer

3 Comments

I think it has to be recursive for the problem he is solving.
@Woot4Moo: "Has to be" in what sense?
@aix: The OP's probably learning how to do recursion in the first place.
2

To elaborate on @Helgi answer, here is a more performant recursive implémentation. It updates the list instead of summing two lists (which results in the creation of a new object every time).

This pattern forces you to pass a list object as third parameter.

def split_word(word, num_of_chars, tail):

    if len(word) > 0:
        tail.append(word[:num_of_chars])
        return split_word(word[num_of_chars:], num_of_chars, tail)

    return tail

res = split_word('fdjskqmfjqdsklmfjm', 3, [])

Another advantage of this form, is that it allows tail recursion optimisation. It's useless in Python because it's not a language that performs such optimisation, but if you translate this code into Erlang or Lisp, you will get it for free.

Remember, in Python you are limited by the recursion stack, and there is no way out of it. This is why recursion is not the preferred method.

You would most likely use generators, using yield and itertools (a module to manipulate generators). Here is a very good example of a function that can split any iterable in chunks:

from itertools import chain, islice

def chunk(seq, chunksize, process=iter):
    it = iter(seq)
    while True:
        yield process(chain([it.next()], islice(it, chunksize - 1)))

Now it's a bit complicated if you start learning Python, so I'm not expecting you to fully get it now, but it's good that you can see this and know it exists. You'll come back to it later (we all did, Python iteration tools are overwhelming at first).

The benefits of this approach are:

  • It can chunk ANY iterable, not just strings, but also lists, dictionaries, tuples, streams, files, sets, queryset, you name it...
  • It accepts iterables of any length, and even one with an unknown length (think bytes stream here).
  • It eats very few memory, as the best thing with generators is that they generate the values on the fly, one by one, and they don't store the previous results before computing the next.
  • It returns chunks of any nature, meaning you can have a chunks of x letters, lists of x items, or even generators spitting out x items (which is the default).
  • It returns a generator, and therefor can be use in a flow of other generators. Piping data from one generator to the other, bash style, is a wonderful Python ability.

To get the same result that with your function, you would do:

In [17]: list(chunk('fdjskqmfjqdsklmfjm', 3, ''.join))
Out[17]: ['fdj', 'skq', 'mfj', 'qds', 'klm', 'fjm']
Improve this answer

1 Comment

Fantastic! I thank you very much for spelling this out in detail. I've learnt a lot from this post (and also from the others in this thread).

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.