Bottom Page

Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
 Recursions with nested lists
#1
I was able to write a function to recursively add the values within a nested list below:

def add_tree(tree):
    """
    Recursively computes the addition of all tree leaves.
    Returns an integer representing the addition.

    Inputs
       tree: A list (potentially containing sublists) that
       represents a tree structure.
    Outputs
       total: An int equal to the addition of all leaves of the tree.

    """

    if not isinstance(tree,list): 
        return tree
    else: 
        sumtree=0 
        for i in tree: 
            sumtree+=add_tree(i)
    return sumtree
This makes sense to me, especially after using Python Tutor.

The next part of my homework question asks us to define a new function that can carry out basic arithmetic operations on the leaves of a tree, i.e., the nested list. Operations are defined for us. I'll use the given addition operation as an example:

def summation(a,b):
    """
    Example operator function.
    Takes in two integers, returns their sum.
    """
    return a + b
In the new function we are asked to define op_tree, which takes three arguments:
op_tree(tree, op, base_call) where tree is the nested list, op is the operation function thus summation in my example, and base_call is the value the function returns when the tree is empty (0 for summation).

op_tree has to be recursive. I'm having trouble starting. It's unclear to me what I'm putting in as the arguments for the op, which requires two: a and b.
Quote
#2
In your function, you have:

sumtree+=add_tree(i)
That is equivalent to:

sumtree = sumtree + add_tree(i)
Given that you want to replace a and b in a + b, what matches from your earlier code?
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures

Quote
#3
(Oct-04-2019, 05:23 PM)ichabod801 Wrote: In your function, you have:
 sumtree+=add_tree(i) 
That is equivalent to:
 sumtree = sumtree + add_tree(i) 
Given that you want to replace a and b in a + b, what matches from your earlier code?

Thank you for the push. I ended up writing this

def op_tree(tree, op, base_case):
    """
    Recursively runs a given operation on tree leaves.
    Return type depends on the specific operation.

    Inputs
       tree: A list (potentially containing sublists) that
       represents a tree structure.
       op: A function that takes in two inputs and returns the
       result of a specific operation on them.
       base_case: What the operation should return as a result
       in the base case (i.e. when the tree is empty).
    """  
  
    if isinstance(tree,int):
        return op(base_case,tree)
        
    else:
        value=op(base_case,base_case)
        for i in tree:
            value+=op_tree2(i,op,base_case)
        return value
Which worked for the summation operation, but does not work for a product operation and I knew it was because I was using +=, which doesn't work for multiplication. However, going back to your comment after I tried this clarified things. I changed the code above incorporating your hint and I got it to work!
Quote

Top Page

Possibly Related Threads...
Thread Author Replies Views Last Post
  Sum of Nested Lists raifuru42 2 1,159 Feb-19-2018, 02:57 PM
Last Post: mckingstar
  Combine nested lists in output python12345 2 770 Feb-17-2018, 01:38 PM
Last Post: python12345
  Nested loops, lists and if statements Liquid_Ocelot 10 3,455 Apr-23-2017, 02:02 PM
Last Post: Mekire

Forum Jump:


Users browsing this thread: 1 Guest(s)