CODEWITHSUNDEEP
pythonrecursion
HoopsMcCann
HoopsMcCann

Reputation: 347

Python Using Recursion to Traverse Through a Nested List With Conditions

Suppose I have the following:

def foo(lst):
  current = 0
  if(len(lst) == 0):
    return current
  first = bar(lst[0])
  rest = foo(lst[1:])
  if(first > current):
    current = first
  return current

if __name__ == "__main__":
  lst1 = [2,4,6]
  lst2 = [0,2,5,6,12]
  lst3 = []
  lst4 = [1]
  lst5 = [2]
  full_lst = [lst1, lst2, lst3, lst4, lst5]
  print(foo(full_lst))

This function takes a nested list in the above structure as a parameter. The goal of the function is to traverse through this nested list structure recursively and apply a computation to each list. The function is also to keep track of each computation and eventually return the largest of these values obtained from the computations.

I believe I have some the basic structure complete, but I fail to see how I could use the function call on the smaller sub list and compare the value obtained from that with the one obtained from the previous function call.

Thanks.

Upvotes: 0

Views: 2382

Answers (3)

Esben Eickhardt
Esben Eickhardt

Reputation: 3852

How about something like this (if you don't want to pop your list):

def traverse_nested_list(my_nested_list):
    results=[]
    for my_item in my_nested_list:
        if not isinstance(my_item, list):
            # Insert condition
            results.append(my_item)
        if isinstance(my_item, list):
            results.append(traverse_nested_list(my_item))
    return results

# Nested list for testing
my_list = [1,2,3,4,5,[6,7,8,[9,1,2,3,4,5,6]]]

# Testing function
traverse_nested_list(my_list)
> [1,2,3,4,5,[6,7,8,[9,1,2,3,4,5,6]]]

Then you can just insert whatever condition you want at the value level. Here an example where we only keep values higher than five:

# Traverser with condition
def traverse_nested_list(my_nested_list):
results=[]
for my_item in my_nested_list:
    if not isinstance(my_item, list):
        if my_item > 5:
            results.append(my_item)
    if isinstance(my_item, list):
        results.append(traverse_nested_list(my_item))
return results

# Nested list for testing
my_list = [1,2,3,4,5,[6,7,8,[9,1,2,3,4,5,6]]]

# Testing function
traverse_nested_list(my_list)
> [[6, 7, 8, [9, 6]]]

Upvotes: 1

John Mee
John Mee

Reputation: 52253

Recursion is fun. Focus on these two things:

  1. If the answer is simple, return it!

    Where does the recursion end? Usually with some foundation like 'if this value in then that value out.'

  2. If the answer is not simple:

    • break into parts
    • ask yourself the answer to the parts
    • recombine the parts into a result

So it's really just about working out where to end the loop, and how to divide/combine the parts.

In your sample you have the end point, but you don't use 'the rest'.

Upvotes: 0

Terry Jan Reedy
Terry Jan Reedy

Reputation: 19144

bar = len

def foo(lst):
    if lst:
        last = lst.pop()
        return max(foo(lst), bar(last))
    else:
        return float('-inf')

if __name__ == "__main__":
    lst1 = [2,4,6]
    lst2 = [0,2,5,6,12]
    lst3 = []
    lst4 = [1]
    lst5 = [2]
    full_lst = [lst1, lst2, lst3, lst4, lst5]
    print(foo([]), foo(full_lst))

# prints '-inf 5'

Upvotes: 0

Related Questions