1

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.

Improve this question
6
  • This is a poor usage of recursion, you have a quadratic algorithm that can't handle lists longer than 1000 elements, much harder to write and much slower. Use list(it). If a CS curriculum is imposing this on you for pedagogical purposes, that's very unfortunate -- they're essentially asking you to mow the lawn with a pair of scissors. Scissors are nice for other things, like cutting paper. Commented Oct 3, 2021 at 1:43
  • @ggorlen I would say this is a classic use of educational recursion in functional languages like Scala or Haskell where a list is typically a linked list. It's certainly not idiomatic Python, but if you're teaching with Python, it seems like a valid way to start reasoning about recursion. Commented Oct 3, 2021 at 1:53
  • Teaching functional programming with Python is like teaching OOP with C. You can do it, but it makes no sense and doesn't do proper justice to the concept and only seems to install bad habits and confuse students, as the constant stream of these sort of posts in the recursion tag attests to. See Why isn't Python very good for functional programming? Commented Oct 3, 2021 at 2:48
  • Saying it's like teaching OOP with C is too strong. Creating things like linked lists or recursion is natural and easy to understand in Python (unlike trying to make classes and objects in C). The alternative is asking people to learn bunch of a bunch languages (learn OOP with C++, then lisp for FP, then javascript or Python to actually do something, etc) or not teaching basic concepts. Commented Oct 3, 2021 at 4:43
  • Yea, this was just for me to understand recursion, in the real world no one would use it instead of list(string), also recursion isn't really faster, so is it even viable to use compared to iterative methods? Commented Oct 3, 2021 at 4:48

4 Answers 4

Reset to default
1

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']
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

head, *rest = s breaks down the rest of the string into a tuple so the recursion is no longer working on a string at that point. This may be a technicality but it is not actually the recursive function that produces the result, it merely converts the tuple to a list.
Sorry @AlainT. this criticism has very little value here. The whole point of this exercise is to understand recursion—nobody would ever use recursion for this in an actual Python implementation when list(s) is available. This is a very clear way to demonstrate it and it's what you will find if you look up textbook recursion for a problem like this. If keeping strings is important to you then return [s[0]] + explode(s[1:]) does that…but it's the same from a pedagogical point of view.
1

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']
>>>
Improve this answer

2 Comments

For sure, but I wanted to learn more about recursion as I have never used it before
@swombhai Yeap! Edited my answer, check out the last code, it's much better :)
0

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)
Improve this answer

1 Comment

I think the point was that this is an exercise in using recursion (they say they have to do it recursively).
-1

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)
Improve this answer

2 Comments

Maybe worth pointing out that the last code example calls the recursive function (2*n) -1 times. So for a simple string like 123456 it makes 11 calls to explode(). And the code list(S[start:end+1]) looks like a slice, but it is always of the form S[1, 2], S[2, 3] etc. You could have just written [S[start]]
That was to cover the case of an empty string but I admit it isn't the clearest nor the most efficient way to do it.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.