Using recursion to find max number of nodes in base 7 tree

Question

First time posting here. Teaching myself python and was curios on how to solve the following problem using recursion. We have a company where every employee has a max of 7 reports. Given depth x of the organization, find the max number of employees including the CEO. This is basically finding the number of max nodes of a binary tree, except instead of base 2 we have base 7.

I was able to solve it linearly using the formula (b**(d+1))/(b-1) where b is the base and d is the depth of the tree.

def MaxNodes(d):
minions = ((7**(d+1)) - 1) / 6
return minions

I also solved it iteratively:

def answer(x):
    minions = 1
    for levels in range(x):
        if (levels == 0):
            minions = 7
        else:
            minions += (minions * 7)
    return minions + 1

So we pretty much have value 1 in level 0, and starting from level 1, we start with value 7 and keep multiplying by 7 and adding to the previous result: 1 + (7x1) + (7x7) + (49x7) ... Sorry if this is very straight forward but I can't wrap my head around how to solve this recursively.

Thanks in advance for your help.

Untested and not recursive: `sum([7**i for i in range(depth)])` — Klaus D., May 19 '16 at 05:18
@KlausD. the question already has the exact formula: `((7**(depth+1)) - 1) // 6` and you don't need `[]` inside `sum()`. — jfs, May 19 '16 at 05:24
You are right @TadhgMcDonald-Jensen, on second look I am not sure why i put an addition there, Should just keep multiplying by 7. Thanks for pointing that out. — tjbadr, May 19 '16 at 18:33

score 0 · Accepted Answer · answered May 19 '16 at 05:15

0

Here's a simple recursive implementation:

def nodes(d):
    if d == 0:
        return 1
    else:
        return 1 + 7 * nodes(d - 1)

print [nodes(i) for i in range(5)] # [1, 8, 57, 400, 2801]

Depth is passed as parameter and when it reaches 0 function returns 1 thus stopping the recursion. Otherwise the function will call itself in order to get the number on lower level, multiply the result with 7 and add current level to it.

answered May 19 '16 at 05:15

niemmi

17,113
7
35
42

Thanks! now that I see it it makes sense. Looks like I need a lot of practice. – tjbadr May 19 '16 at 18:33

score 0 · Answer 2 · answered May 19 '16 at 05:45

0

if you want to find 7**x recursively:

def max_siblings(depth, degree=7, total=1):
    """How many siblings maximum at the given *depth*."""
    return max_siblings(depth-1, degree, total*degree) if depth else total

If you want to find ((7**(depth+1)) - 1) // 6 recursively:

def max_nodes(depth, degree=7, total=1):
    return max_nodes(depth-1, degree, total+max_siblings(depth)) if depth else total

Example:

for depth in range(5): 
    print(max_nodes(depth))

Output:

You could cache max_siblings() computations using @lru_cache(maxsize=None) decorator

answered May 19 '16 at 05:45

jfs

399,953
195
994
1,670

Is there a reason to pass the `total` value up the call tree, rather than doing the math on the return values? E.g. `def max_siblings(depth, degree=7): return max_siblings(depth-1, degree) * degree if depth else 1` and `def max_nodes(depth, degree=7): return max_nodes(depth-1, degree) + max_siblings(depth) if depth else 1)`? Cpython at least doesn't do any tail-call elimination. – Blckknght May 19 '16 at 06:00
@Blckknght: [this is the reason](http://stackoverflow.com/questions/13274207/python3-recursivley-sum-digits-of-an-integer/13274806#comment18103138_13274806). Related [discussion](http://stackoverflow.com/questions/17127355/python-recursive-function-that-prints-from-0-to-n/17127379#comment24784883_17127379). Here's [TCO decorator](https://github.com/lihaoyi/macropy#tail-call-optimization). – jfs May 19 '16 at 06:02
I like using defaults to shorten the implementation. Thanks! – tjbadr May 19 '16 at 18:34

Using recursion to find max number of nodes in base 7 tree

2 Answers2