returning from recursive function in python

Question

I am somewhat inexperienced with programming, and I am a little confused about how the return function works. I am trying to write a program that maps a function onto the elements of a nested list. The variable levels represents the number of times nested levels there are in the list. I currently can get the program to work by printing my final mapped list, totlist:

def map_nested(listbasket, function, levels): #listbasket is the list that contains lists
    totlist=[] #this list will store the list after the function has been mapped to it
    for listelement in listbasket:

        if levels<=2: #once we get to the level that just contains a list of lists
            newlist=list(map(function,listelement)) 
            totlist.append(newlist) #add to final mapped list

        else:
            map_nested(listelement, function, levels-1) #recursively call for next level
    print(totlist)  

map_nested([[[1,2],[3,4]],[[5,6],[7,8]]], math.sqrt, 3) # my test function

Instead, I want something that returns the totlist, but I can't figure out how to do this. everytime I try returning it, it just returns an empty list or part of the list. I feel like i've tried every configuration of returns I can think of.

did you try and replace print(totlist) with return totlist? — bj0
– bj0, Commented Feb 18, 2014 at 22:38
You say that it prints correctly, if you literally make that substitution it will return what it is printing. You have to remember to assign that return value to a variable at the call site and print it out there. — bj0
– bj0, Commented Feb 18, 2014 at 22:57
I actually tried that already. It didn't work. when I printed the variable, it printed [] — Beth
– Beth, Commented Feb 18, 2014 at 23:04
Oh I see what you meant, the print also prints "[]" for the outermost call. From your description I thought you were saying that it was correct. Because of the recursive nature you have to propagate the return values of the recursive calls back out, which Kaarel's answer does very cleanly. — bj0
– bj0, Commented Feb 18, 2014 at 23:27
Can you explain how Kaarel's first answer works? I don't understand how you can append totlist with a function that sets totlist to 0. — Beth
– Beth, Commented Feb 18, 2014 at 23:43

Kaarel Nummert · Accepted Answer · 2014-02-18 22:56:57Z

2

This will work:

import math

def map_nested(listbasket, function, levels): #listbasket is the list that contains lists
    totlist=[] #this list will store the list after the function has been mapped to it
    for listelement in listbasket:

        if levels<=2: #once we get to the level that just contains a list of lists
            newlist=list(map(function,listelement)) 
            totlist.append(newlist) #add to final mapped list
        else:
            totlist.append(map_nested(listelement, function, levels-1))
    return totlist

map_nested([[[1,2],[3,4]],[[5,6],[7,8]]], math.sqrt, 3) # my test function

or a slightly neater solution:

import math

def map_nested(input, function):
    if type(input) is list:
        return [map_nested(e, function) for e in input]
    else:
        return function(input)

print map_nested([[[1,2],[3,4]],[[5,6],[7,8]]], math.sqrt)

This is recursively applying the map_nested method to every list in your hierarchy. When the recursion reaches an element in a list, it applies the function provided in the original call.

Note that this works on arbitrarily deeply nested lists, and also works on unbalanced nested lists (e.g., [1, 2, [3, 4]]).

edited Feb 18, 2014 at 22:56

answered Feb 18, 2014 at 22:39

Kaarel Nummert

9998 silver badges20 bronze badges

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

1 Comment

Beth Over a year ago

Thanks, this is exactly what I was looking for. However, I am not really sure I understand how it works. It seems like appending the function would end up adding on elements multiple times. Can you explain a little bit about what is going on here?

jonrsharpe · Accepted Answer · 2014-02-18 22:45:44Z

I would make totlist an argument:

def map_nested(listbasket, function, levels, totlist=None):
    if totlist is None:
        totlist = []
    for listelement in listbasket:
        if levels <= 2:
            newlist = list(map(function, listelement)) 
            totlist.append(newlist) #add to final mapped list
        else:
            map_nested(listelement, function, levels-1, totlist)
    return totlist

Now:

>>> map_nested([[[1,2],[3,4]],[[5,6],[7,8]]], math.sqrt, 3)
[[1.0, 1.4142135623730951], 
 [1.7320508075688772, 2.0], 
 [2.23606797749979, 2.449489742783178], 
 [2.6457513110645907, 2.8284271247461903]]

If you want to simplify (not manually passing levels) and flatten the nest as you go, something like:

def map_nested_2(lst, f, out=None):
    if out is None:
        out = []
    for item in lst:
        if isinstance(item, list):
            map_nested_2(item, f, out)
        else:
            out.append(f(item))
    return out

Would give:

[1.0, 1.4142135623730951, 1.7320508075688772, 2.0, 2.23606797749979, 
 2.449489742783178, 2.6457513110645907, 2.8284271247461903]

Collectives™ on Stack Overflow

returning from recursive function in python

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related