CODEWITHSUNDEEP
pythonstringlistrecursion
Swayam Shah
Swayam Shah

Reputation: 210

How can I use recursion to convert a string to list of characters in Python?

I have to split a string for example 'star' to a list like ['s','t','a','r'] and have to do it recursively. I know how to do this iteratively but not recursively.

Below is my code to do so but it rightly does not work.

def explode(S):
    res = []
    res.append(S[0])
    if len(S)==1:
        return res
    else:
        res.append(explode(S[1:]))
    return res

The output I get is:

['s', ['t', ['a', ['r']]]]

How do I fix this? Is there an example from which I can learn recursion better because this clearly does not work.

Upvotes: 1

Views: 2512

Answers (4)

Alain T.
Alain T.

Reputation: 42143

You could do it with a default parameter that gives you the index of the character to add to the result (this will be more efficient than passing substrings down the recursion):

def explode(S,i=0):
    return [S[i]] + explode(S,i+1) if i<len(S) else []

print(explode('Hello World!'))
['H', 'e', 'l', 'l', 'o', ' ', 'W', 'o', 'r', 'l', 'd', '!']

The main issue with this solution (and others like it) is that it will hit the maximum recursion depth when the length of the string gets near 992.

To avoid that, you can divide the work in half and recurse twice at each level (which will theoretically allow the function to operate on strings of nearly 2^1000 characters):

def explode(S,start=0,end=None):
    if end is None: end = len(S)-1
    if start>=end: return list(S[start:end+1])
    mid = (start+end)//2
    return explode(S,start,mid) + explode(S,mid+1,end)

Upvotes: -1

Agent47
Agent47

Reputation: 101

A straightforward way to do it would be to convert it into list.

Let's say you have a string

s = "star"

Converting a string into list can be done by using list()

converted = list(s)

Upvotes: 0

U13-Forward
U13-Forward

Reputation: 71570

Try extend instead of append:

def explode(S):
    res = []
    res.append(S[0])
    if len(S)==1:
        return res
    else:
        res.extend(explode(S[1:]))
    return res

Output:

>>> explode('star')
['s', 't', 'a', 'r']
>>>

But you could simply just use the list function:

>>> list('star')
['s', 't', 'a', 'r']
>>>

Another recursive idea which is similar to @Mark's but with generators:

def explode(S):
    if not S:
        return []
    it = iter(S)
    return [next(it)] + explode(list(it))

Ex:

>>> explode('star')
['s', 't', 'a', 'r']
>>>

Upvotes: 1

Mark
Mark

Reputation: 92440

Typically with recursion, you should first think base case — here an empty string. Then take a part of the input and recurse on the rest.

In this case you don't even need to manually instantiate a list...just do it in the base case and you avoid extend/append altogether:

def explode(s):
    if not s:                       # base case
        return []
    head, *rest = s                 # take a piece
    return [head] + explode(rest)   # pass the rest back in

explode('star')
# ['s', 't', 'a', 'r']

Upvotes: 1

Related Questions