Recursion and how to improve a program in python

Question

Hi I'm new to programming and I'm learning python. I'm currently learning recursion and I'm finding it kind of difficult. I found this exercise:

Write a function "flatten" that returns a simple list containing all the values in a nested list

Then the exercise gives these test runs:

test(flatten([2,9,[2,1,13,2],8,[2,6]]) == [2,9,2,1,13,2,8,2,6])
test(flatten([[9,[7,1,13,2],8],[7,6]]) == [9,7,1,13,2,8,7,6])
test(flatten([[9,[7,1,13,2],8],[2,6]]) == [9,7,1,13,2,8,2,6])
test(flatten([["this",["a",["thing"],"a"],"is"],["a","easy"]]) == ["this","a","thing","a","is","a","easy"])
test(flatten([]) == [])

I did this:

new_list = []

def flatten(a_list):  

    for e in a_list:
        if type(e) != type([]):
            new_list.append(e)
        if type(e) == type([]):
            flatten(e)

    print(new_list)
    return new_list

and then added new_list.clear() between all the test runs like this:

test(flatten([2,9,[2,1,13,2],8,[2,6]]) == [2,9,2,1,13,2,8,2,6])
new_list.clear()
test(flatten([[9,[7,1,13,2],8],[7,6]]) == [9,7,1,13,2,8,7,6])
new_list.clear()
test(flatten([[9,[7,1,13,2],8],[2,6]]) == [9,7,1,13,2,8,2,6])
new_list.clear()
test(flatten([["this",["a",["thing"],"a"],"is"],["a","easy"]]) == 
["this","a","thing","a","is","a","easy"])
new_list.clear()
test(flatten([]) == [])
new_list.clear()

It works.

The problem is I feel like there's a better way to do it so I'm asking for help so that I can learn from you. Thanks for the help.

Edit: The "print(new_list)" part was me trying to understand what was going on in the program.

hsnsd · Accepted Answer · 2018-07-21 15:00:20Z

3

I can not comment whether your way is better or mine. But when I was learning recursion, I was told to avoid loops in recursion wherever possible, to get a proper understanding of the concept.

So here is a way you can do this without any loops. Feel free to ask if you dont get anything from the code below.

new_list = []
def flatten(a_list):
    if len(a_list) != 0:
        if type(a_list[0]) != type([]):
            new_list.append(a_list[0])
            flatten(a_list[1:])
        else:
            flatten(a_list[0])
            flatten(a_list[1:])
    return new_list

answered Jul 21, 2018 at 15:00

hsnsd

1,8231 gold badge21 silver badges36 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Domenico Agosta Over a year ago

oh, ok. I see. This is kind of an interaction I didnt know about. I didnt know that you could this part: flatten(a_list[1:]) I just assumed you couldnt do it beacuse you were not using a list but never bothered to try.

Domenico Agosta Over a year ago

Thanks for your suggestion. I'll definitely take your advice to avoid loops. I think that's the hardest part to take count of when doing this kind of exercises.

hsnsd Over a year ago

it gets easy as you practice more and more :)

cdlane · Accepted Answer · 2018-07-23 04:01:23Z

when I was learning recursion, I was told to avoid loops in recursion wherever possible

I was never taught that, but I did learn to avoid setting a global as a means of returning something from a recursive function. How's this as an alternative:

def flatten(a_list):
    new_list = []

    if a_list:  # Python idiom for a non-empty container

        head, *tail = a_list  # fun with Python-3.x

        if isinstance(head, list):
            new_list.extend(flatten(head))
        else:
            new_list.append(head)

        new_list.extend(flatten(tail))

    return new_list

And get rid of that top level new_list = [] statement. You won't need to add a new_list.clear() between all the test runs as flatten() now returns its result instead of setting a global.

Collectives™ on Stack Overflow

Recursion and how to improve a program in python

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related