0

我最近被提出了这个问题，但不太擅长编写递归函数。你会怎么解决？

您的公司结构如下：

#          employee: manager
company = {
           '17': '15', 
           '16': '15',
           '10': '5', 
           '15': '10',  
           '5': '4', 
           '4': 'NULL'
           }

每个数字都是人的身份证。第 4 个人是 CEO，因为没有经理，所以它的值为 NULL。你怎么能写一个reportsTo(eid, mid)返回的递归函数：

  • reportsTo('17', '4')-->True
  • reportsTo('15', '16')-->False
4

4 回答 4

5 
  def reportsTo(eid, mid):
       m2 = company[eid]
       if m2 == "NULL": return False
       return m2 == mid or reportsTo(m2, mid)
于 2013-11-07T16:35:53.137 回答
3

制作递归函数的第一步是确定基本情况。这有两个。

  1. 员工直接向经理汇报：返回真。
  2. 员工的经理为空：返回 false，因为我们已经联系到 CEO。

如果我们已经走到这一步，我们会返回对同一函数的调用，使用 company[e] 而不是原来的雇员。它沿着链条向上，直到到达基本案例之一。

这只有在员工只有一名直接经理时才有效。如果有更多，它会变得更加复杂。

于 2013-11-07T16:54:40.917 回答
1

如果我明白你想做什么，你可以做这样的事情（伪代码）：

function reportsTo(eid, mid):
    if company[eid] is mid          # base case number 1
        return True
    else if company[eid] is null    # base case number 2
        return False
    else
        return reportsTo(company[eid], mid)

如果您想了解递归函数，我会尝试实现非常琐碎的事情，但要递归。例如，创建一对递归函数，一个检查数字是否为偶数，一个检查是否为奇数。

编辑：

Python：

def reportsTo(eid, mid):
    if company[eid] == mid:          # base case number 1
        return True
    elif company[eid] is None:    # base case number 2
        return False
    else
        return reportsTo(company[eid], mid)

（我将 CEO 的经理改为None而不是一个字符串，'NULL'因为这对我来说似乎更好）。

或者：

def reportsTo(eid, mid):
    if eid in company:
        return False
    return (eid == mid) or (reportsTo(company[eid], mid))
于 2013-11-07T16:34:58.277 回答
1

这是一个使用递归的快速解决方案：

def reportsTo(e, m):
    if e == 'NULL':
        return False
    assert e in company
    if m == company[e]:
        return True
    else:
        return reportsTo(company[e], m)

编辑虽然上面的代码在技术上是正确的，但尝试改进它是一个很好的练习。

根据其他人的评论：

  • 不需要断言。company[e]如果密钥不存在，将引发 a KeyError，因此可以删除此代码。
  • company[e]可能不止一次计算。为了速度和可读性，将其分配给局部变量。
  • e存在的检查'NULL'可以移动到company[e]存在的检查'NULL'；这可以节省一个函数调用。
  • -可以变成if，利用它的左参数是惰性的和严格的事实，即它不会评估其右参数，因此该函数不会递归，只要它的左参数是)。elseororTrue
于 2013-11-07T16:36:39.487 回答