使用递归查找基7中的最大节点数

Question

第一次在这里发布。我自学python，对如何使用递归解决以下问题很感兴趣。 我们有一个公司，每个员工最多有7份报告。给定组织的深度x，找出包括CEO在内的最大员工数。这基本上就是求一个二叉树的最大节点数，除了用基数7代替基数2。你知道吗

我可以用公式（b**（d+1））/（b-1）线性求解，其中b是基，d是树的深度。你知道吗

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

我还迭代求解：

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

所以我们在0级中基本上有值1，从1级开始，我们从值7开始，一直乘以7，再加上前面的结果： 1+（7x1）+（7x7）+（49x7）。。。 抱歉，如果这是非常直截了当，但我不能围绕我的头怎么解决这个递归。你知道吗

事先谢谢你的帮助。你知道吗

Answer 1

如果要递归查找7**x：

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

如果要递归查找((7**(depth+1)) - 1) // 6：

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

示例：

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

输出：

1
8
57
400
2801

可以使用^{} decorator缓存max_siblings()计算

Answer 2

下面是一个简单的递归实现：

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]

深度作为参数传递，当它达到0时，函数返回1，从而停止递归。否则，函数将调用自身以获得较低级别的数字，将结果乘以7并将当前级别相加。你知道吗