How do i split strings with recursion in Python?

Question

I wanted to ask how to create a recursive function that splits every string that is contained in a list for every character, removing one from the beginning each time that I repeat the process. I also want to do this but by removing a letter from the end each time. for example, if I have something like:

list=['house','cat','dog']

I should get

['house','ouse','use','se','e','cat','at','t','dog','og','g']

and

['house','hous','hou','ho','h','cat','ca','c','dog','do','d']

i tried to do this but it doesn't work; also, it should be all recursive... thank you in advance.

def substring(stringslist):
    final=[]
    for string in stringslist:
        if len(string)==1:
            return final.append(string)
        else:
            return final.append(substring(string[::-1]))

Hint: Recursion is much easier without mutability, i.e. don't use [] and append. Use () and +. — MisterMiyagi
– MisterMiyagi, Commented Feb 13, 2020 at 15:13

mingmingrr · Accepted Answer · 2020-02-13 15:41:23Z

First, let's fix your function into an iterative version that works.

def substring(strings):
    final = []
    for string in strings:
        while string:
            final.append(string)
            string = string[1:]
    return final

Next, let's move the final variable into the arguments so that recursive calls to the function can build upon the list.

def substring(strings, final=None):
    if final is None: final = []
    for string in strings:
        while string:
            final.append(string)
            string = string[1:]
    return final

The next step is to convert the for loop into recursion. We can see that the base case is when the list strings is empty, and the recursive case is to work on each element of strings. For the recursive case here we'll extract the first element of strings and pass the rest of the list to the recursive call.

def substring(strings, final=None):
    if final is None: final = []
    # base case: empty list
    if not strings: return final
    # recursive case:
    # work on first string in list
    string = strings[0]
    # add all substrings to final
    while string:
        final.append(string)
        string = string[1:]
    return substring(strings[1:], final)

Converting the while loop into recursion is a similar process: find the base case (empty string) and the recursive case (adding a single substring to final), and make a recursive call for the recursive case.

def substring(strings, final=None):
    if final is None: final = []
    if not strings: return final
    string = strings[0]
    if not string: return substring(strings[1:], final)
    final.append(string)
    strings[0] = string[1:]
    return substring(strings, final)

And finally, a bit of cleanup.

def substring(strings, final=None):
    if final is None: final = []
    if not strings: return final
    if not string[0]: return substring(strings[1:], final)
    final.append(string)
    strings[0] = string[0][1:]
    return substring(strings, final)

Green Cloak Guy · Accepted Answer · 2020-02-13 15:27:59Z

1

Using a generator makes for a more straightforward implementation - you just have to cast the result to a list().

lst=['house','cat','dog']

def substring(string, reversed=False):
    if string:  # if string is not zero-length:
        yield string  # yield its full length
        yield from substring(string[:-1] if reversed else string[1:])  # and recurse

def substrings(stringslist, reversed=False):
    for string in stringslist:
        yield from substring(string, reversed)

>>> list(substrings(lst))
['house', 'ouse', 'use', 'se', 'e', 'cat', 'at', 't', 'dog', 'og', 'g']
>>> list(substrings(lst, reversed=True))
['house', 'hous', 'ous', 'us', 's', 'cat', 'ca', 'a', 'dog', 'do', 'o']

answered Feb 13, 2020 at 15:27

Green Cloak Guy

24.8k4 gold badges39 silver badges58 bronze badges

Comments

jawad-khan · Accepted Answer · 2020-02-13 15:29:22Z

1

In case you want recursion, this will do the job. I have written it only for one case but you can flip it for other easily.

def substring(stringslist):
    final = []
    for string in stringslist:
        final.append(string)
        if len(string)==1:
            return final
        else:
            final.extend(substring([string[:-1]]))

    return final

answered Feb 13, 2020 at 15:29

jawad-khan

3131 silver badge10 bronze badges

Comments

Kennos · Accepted Answer · 2020-02-13 15:36:15Z

1

The following code should work for you:

list=['house','cat','dog']
final=[]

for word in list:
    for i in range(len(word)):
        final.append(word[i:])

print(final)

output: ['house', 'ouse', 'use', 'se', 'e', 'cat', 'at', 't', 'dog', 'og', 'g']

Here i'm iterating over the list, and for every word in the list im again interating over the letters to determine the number of items to be added to the final list.

answered Feb 13, 2020 at 15:36

Kennos

2371 silver badge6 bronze badges

Comments

gsb22 · Accepted Answer · 2020-02-13 15:23:58Z

0

I have used nested for loops for clarity but you could use list comprehension for shorter code.

Use enumerate() for getting index, so that you can do the substring manipulation.

IDLE Output:

>>> new_list1 = []
>>> new_list2 = []
>>> for item in my_list:
        for index, value in enumerate(item):
            new_list1.append(item[:len(item)-index])
            new_list2.append(item[index:])


>>> new_list1
['house', 'hous', 'hou', 'ho', 'h', 'cat', 'ca', 'c', 'dog', 'do', 'd']
>>> new_list2
['house', 'ouse', 'use', 'se', 'e', 'cat', 'at', 't', 'dog', 'og', 'g']

answered Feb 13, 2020 at 15:23

gsb22

2,2002 gold badges12 silver badges28 bronze badges

Comments

Phoenixo · Accepted Answer · 2020-02-13 15:28:21Z

0

Here is a recursive way to do it for one string, and I added a for loop, you can get inspiration from that :

L = ['house','cat','dog']
final = []
def substring(s):
    global final
    if len(s)==1:
        final.append(s)
    else:
        final.append(s)
        substring(s[:-1])
    return final

for s in L:
    substring(s)
print(final)
# ['house', 'hous', 'hou', 'ho', 'h', 'cat', 'ca', 'c', 'dog', 'do', 'd']

answered Feb 13, 2020 at 15:28

Phoenixo

2,1631 gold badge9 silver badges14 bronze badges

Collectives™ on Stack Overflow

How do i split strings with recursion in Python?

6 Answers 6

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related