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

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.

CodePudding user response：

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']

CodePudding user response：

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']
>>>

CodePudding user response：

You could do it with a default parameter that gives you the index of the character to add to the result:

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', '!']

CodePudding user response：

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)