Python recursive function to create generic tree

Question

I'm trying to create a tree with n children for each node. Problem is, when I try to implement this using a recursive function, I ends up with multiple recursive calls so I can't have a single return statement, hence having None as a final result.

Here is my piece of code :

def recursive_func(tree, n):
    if n == 0:
        return tree
    else:
        permutations = get_permutations()
        for permutation in permutations:
            child_tree = recursive_func(Tree(permutation), n-1)
            tree.addChild(child_tree)

get_permutations() gives a list of child trees to create. I also have a Tree class with a node value and a list of children.

Here is the Tree class:

class Tree:
    def __init__(self, result):
        self.node = node
        self.children = []

    def addChild(self, tree):
        self.children.append(tree)

This is probably a rookie error in the design of my problem, but I would be glad to get some help.

you say `I ends up with multiple recursive calls` Can you please show us the output? Also no need to say this is probably a rookie error, no one will get mad, well most people won't, if you post something that is formatted properly! — Glenville Pecor, Feb 14 '20 at 18:06
`tree.addChild()` returns nothing, it just appends the child to the tree. I updated my post with the Tree class. As for the mention of multiple recursive calls, it is just because I have a for loop within the recursive call. — Beinje, Feb 17 '20 at 10:10
Why don't you just use *multiple* ``return`` statements or have one final ``return`` at the end (and remove the first branch)? It seems that the function should always ``return tree`` for all current branches. — MisterMiyagi, Feb 17 '20 at 10:18
Well, looks like it works @MisterMiyagi ! But I still don't really get why because I don't need `recursive_func()` to return something at the end so I thought the return statement within the `n == 0` condition was sufficient for the recursive function to run through the entire tree. Yet, it seems that I need to `return tree` anyway, right ? — Beinje, Feb 17 '20 at 11:49
Since you are using the result (in ``child_tree = recursive_func(…)``), yes, you should consistently return something. — MisterMiyagi, Feb 17 '20 at 11:58
OK, I think I get it. Should I answer my own question with a mention to your comment ? — Beinje, Feb 17 '20 at 12:53

score 1 · Accepted Answer · answered Feb 18 '20 at 11:55

TLDR: Since you use the result of recursive_func, it should always return its tree.

The recursive_func has three important points for this problem:

def recursive_func(tree, n):
    if n == 0:
        return tree  # 1.
    else:
        permutations = get_permutations()
        for permutation in permutations:
            child_tree = recursive_func(Tree(permutation), n-1)  # 2.
            tree.addChild(child_tree)
    # 3.

Now, 1. defines that the function sometimes returns a Tree. This matches 2. which always expects the function to return a Tree. However, both conflict with 3., which implicitly returns None when the second branch is done.

Since the first branch is empty aside from the return, both 1. and 3. can be collapsed to one path that always returns a Tree.

def recursive_func(tree, n):
    if n > 0:
        permutations = get_permutations()
        for permutation in permutations:
            child_tree = recursive_func(Tree(permutation), n-1)
            tree.addChild(child_tree)
    return tree

Python recursive function to create generic tree

1 Answers1