0

The problem that I had to tackle was creating a function that recursively flattens a nested list.

The following below is my code.

What I don't understand is how the program keeps returning an empty list. I realize that I had to initialize an empty list and that could be the problem here but how else could I tackle this?

def flat_list(nested_lst, low, high):
   new_lst = []

   if low >= high:
       return new_lst

   if type(nested_lst[low]) is list:
       for item in nested_lst[low]:
           new_lst.append(item)
       return flat_list(nested_lst, low+1, high)
    
   else:
       new_lst.append(nested_lst[low])
       return flat_list(nested_lst, low+1, high)


def main():
   lst = [[1], [[2, [3], 4], 5], 6]

   print(flat_list(lst, 0, len(lst)-1))


main()
Improve this question
7
  • 1
    Use an IDE like Pycharm to track each recursion cycle. That'll help you a lot. Commented Jul 24, 2020 at 2:00
  • I followed the first comment's advice and it seems like the function is creating a new empty list every recursive cycle but I don't understand how else to define the list and append to it? Commented Jul 24, 2020 at 2:04
  • 1
    It isn't clear how the parameters low and high are even relevant to the problem. You seem to be over-complicating it. Commented Jul 24, 2020 at 2:05
  • 1
    "The low and high were required for the problem" -- not in the problem that you described in the question that you posted, which was simply about flattening a nested list. Commented Jul 24, 2020 at 2:09
  • 1
    Define one function that is independent of low and high. Then another function will call that with the appropriate slice of the original list, then replacing the slice with the flattened returned value. Commented Jul 24, 2020 at 2:10

3 Answers 3

Reset to default
2

I think this clause is exemplary of your problems:

   for item in nested_lst[low]:
       new_lst.append(item)
   return flat_list(nested_lst, low+1, high)

You append stuff onto new_lst, then completely ignore it in your returned result!

The larger problem, typical of folks new to recursion, is insisting on sticking a for in the middle of your recursive function! The key is to think recursively, and trust recursion to do the work:

def flat_list(nested_lst):
    if nested_lst:
        head, *tail = nested_lst

        return (flat_list(head) if isinstance(head, list) else [head]) + flat_list(tail)

    return nested_lst

if __name__ == "__main__":
    lst = [[1], [[2, [3], 4], 5], 6]

    print(flat_list(lst))

You see that it can be done without low and high, so now it's a matter of adding them back since you're required to use them.

that code that @RufusVS posted is to go inside the flattening function or does it go in the main function?

I pesonally would say, "neither". I'd wrap the code of @RufusVS around my recursive function:

def flat_list(nested_list, low, high):

    def flat_list_recursive(nested_lst):
        if nested_lst:
            head, *tail = nested_lst

            head = flat_list_recursive(head) if isinstance(head, list) else [head]

            return head + flat_list_recursive(tail)

        return nested_lst

    new_list = list(nested_list) # shallow copy

    new_list[low:high] = flat_list_recursive(nested_list[low:high])

    return new_list
 
if __name__ == "__main__":
    lst = [[1], [[2, [3], 4], 5], 6]

    print(flat_list(lst, 1, 2))  # [[1], 2, 3, 4, 5, 6]
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

In this context, asterisk is an unpacking operator. The first element of nested_list gets put into head, the reading elements get put into tail. Equivalent to head, tail = nested_list[0], nested_list[1:]
So, in light of my other comment, you can call this excellent function with: something close to: orig_list[low:high]=flat_list(orig_list[low:high]) to fit the original requirements.
that code that @RufusVS posted is to go inside the flattening function or does it go in the main function?
2

Either of the functions can be coerced into using low and high by doing something like:

def flat_list(nested_list, low=None, high=None):   # arguments are optional
    if low is None:
        # put block contents of either no-arg answers in here
    else:
        nested_list[low:high]=flat_list(nested_list[low:high])
        return nested_list
Improve this answer

2 Comments

My concern is that this would modify the argument nested_list so I used a shallow copy in my implementation of your approach.
@cdlane - you are right. This is actually the first time I've ever actually done assignment to a slice. using return nested_list[:low]+flat_list(nested_list[low:high))+nested_list[high:] might be better than slice assignment for the reason you give.
1

A more readable example:

def flat_list(nested_lst):
   new_lst = []
   
   if type(nested_lst) is list:
       for item in nested_lst:
           new_lst += flat_list(item)
   else:
       new_lst.append(nested_lst)
       
   return new_lst

If you pursue a 'purer' recursive function, remove the for loop. It would be like:

def flat_list(nested_lst):
   if not nested_lst:
       return []
   
   head, *tail = nested_lst
   if type(head) is list:
      return flat_list(head) + flat_list(tail)
   else:
      return [head] + flat_list(tail)
Improve this answer

3 Comments

Interesting, how could you incorporate high and low parameters into this?
Added an answer using low and high arguments.
@Sesame If you just want flat a list, low and high is not necessary for such work. I just new another list in every iteration by remove low and high. If you want to avoid extra construct you can add high/low point back.

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.