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.

Swayam Shah
  • 200
  • 1
  • 12
  • 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. – ggorlen Oct 03 '21 at 01: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. – Mark Oct 03 '21 at 01: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 [tag:recursion] tag attests to. See [Why isn't Python very good for functional programming?](https://stackoverflow.com/questions/1017621/why-isnt-python-very-good-for-functional-programming) – ggorlen Oct 03 '21 at 02: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. – Mark Oct 03 '21 at 04: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? – Swayam Shah Oct 03 '21 at 04:48
  • @swombhai recursion in python is useful when it can significantly improve the readability (such as traversing nested structures) and you can know the hit to performance won't cause problems. For something like this, it's helpful to understand principles, but not really viable since function calls and building the temporary lists and strings is not free (in terms of performance) and options are available that are more performant and idiomatic. – Mark Oct 03 '21 at 05:19

4 Answers4

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']
>>>
U13-Forward
  • 69,221
  • 14
  • 89
  • 114
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']
Mark
  • 90,562
  • 7
  • 108
  • 148
  • `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. – Alain T. Oct 03 '21 at 04:07
  • 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. – Mark Oct 03 '21 at 04:30
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)
Agent47
  • 91
  • 7
  • 1
    I think the point was that this is an exercise in using recursion (they say they `have to do it recursively`). – Mark Oct 03 '21 at 01:48
-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)
Alain T.
  • 40,517
  • 4
  • 31
  • 51
  • 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]]` – Mark Oct 03 '21 at 05:08
  • 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. – Alain T. Oct 03 '21 at 05:21