CODEWITHSUNDEEP
pythonrecursioniteration
james_weasel
james_weasel

Reputation: 25

Creating an Iterative function instead of Recursive in python

def sum(root):
    if root.children == []:
        return root.value
    else:
        temp = 0
        for n in root.children:
            temp += sum(n)
        temp+= root.value
    return temp

I got my function to work recursively and am trying to figure out an easy way to do it iteratively. I just am trying to find guidance as to if I would be using a while loop or what.

Upvotes: 0

Views: 994

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1121486

Use a queue or stack; take an element from your queue or stack, add the value to the running total, add any children to the queue or stack, then process the next element. Use a while loop that ends when your queue or stack is empty.

The only difference between a stack and a queue is that you'll either process your elements depth first (stack) or breath first (queue).

Your recursive code is depth-first, so to replicate the same behaviour iteratively, use a stack:

def sum_nodes_iteratively(root):
    elements = [root]
    total = 0
    while elements:
        element = elements.pop()
        elements.extend(element.children)
        total += element.value
    return total

Demo:

>>> class Node(object):
...     def __init__(self, value, children):
...         self.value = value
...         self.children = children
...
>>> def sum_nodes_iteratively(root):
...     elements = [root]
...     total = 0
...     while elements:
...         element = elements.pop()
...         elements.extend(element.children)
...         total += element.value
...     return total
...
>>> sum_nodes_iteratively(Node(1,[Node(2,[]),Node(3,[Node(4,[Node(5,[]),Node(6,[Node(7,[])])])])]))
28

Upvotes: 4

Related Questions