CODEWITHSUNDEEP
pythonrecursionmutation
DigitalSoul
DigitalSoul

Reputation: 139

Recursion and List Mutation

I am restrict myself to mutate a list using recursion only, I have a few small troubles when doing so.

def expand_strings(L,s,i):
    if len(L) == 0:
        return
    else:
        if len(L[0]) - 1 <= i:
            L[0] += s
        elif len(L[0]) - 1 > i:
            new_string = L[0][:i] + s + L[0][i:]
            L[0] = new_string
            expand_strings(L[1:], s, i)
            return

L: The input list containing possible 1 or more strings s: The extra portion of string that I need to "insert" or "append" to the string elements within the list i: The index of string where I want to insert or append s to.

The main goal of this function is the following:

1. if the index i within the range 0 ~ len(string_element_in_list), then I insert my s starting from index i


2. if the index i is larger than what the current string length, then I do the append s.

The problems I am having right now is that: I notice the recursion will only mutate the first element within the input list, and every element after the first element, they won't be affected by the mutation, I figure it might have something to do with the new input list I pass to the recursion, but I don't know precisely why this doesn't work.

Thanks for helping in advance. :)

Upvotes: 0

Views: 1093

Answers (1)

Sufian Latif
Sufian Latif

Reputation: 13356

The problem is in the recursive call expand_strings(L[1:], s, i). When you use slicing to get a part of your list, python creates a whole new copy of that sublist. So the recursive call creates a copy of your list, except the first element, and works on that copy.

One way of solving this problem can be returning the modified list from your method:

def expand_strings(L,s,i):
    if len(L) == 0:
        return []
    else:
        if len(L[0]) - 1 <= i:
            L[0] += s
        elif len(L[0]) - 1 > i:
            new_string = L[0][:i] + s + L[0][i:]
            L[0] = new_string
        return [L[0]] + expand_strings(L[1:], s, i)

If you don't want to create a copy of the sublist every time (and return the modified list), you can add one more parameter to your method that would specify the location of the first element to modify. The base case would be where the starting index is equal to the length of the list.

def expand_strings(L,s,i,start):
    if start == len(L):
        return
    if len(L[start]) - 1 <= i:
        L[start] += s
    else:
        L[start] = L[start][:i] + s + L[start][i:]
    expand_strings(L, s, i, start + 1)

Upvotes: 4

Related Questions