1

我正在研究如何像计算机科学家一样思考，目前正在尝试掌握递归。我在其中一个问题上遇到了麻烦，所以我希望你能帮助我。

我正在编写一个函数，它找到一个列表的递归最小值，其元素是整数、整数列表、整数列表列表等。

这是我当前的版本：

def recursive_min(nested_num_list):
    """
      >>> recursive_min([9, [1, 13], 2, 8, 6])
      1
      >>> recursive_min([2, [[100, 1], 90], [10, 13], 8, 6])
      1
      >>> recursive_min([2, [[13, -7], 90], [1, 100], 8, 6])
      -7
      >>> recursive_min([[[-13, 7], 90], 2, [1, 100], 8, 6])
      -13
    """
    min = nested_num_list[0]
    while type(min) == type([]):
        min = min[0]
    for item in nested_num_list:
        if type(item) == type([]):
            recursive_min(item)
        elif item < min:
            min = item
    return min

但是，这只适用于在顶层找到最小值，所以我现在的代码没有进入列表的深度。

现在，看看答案，我知道我的版本应该是这样的：

def recursive_min(nested_num_list):
    """
      >>> recursive_min([9, [1, 13], 2, 8, 6])
      1
      >>> recursive_min([2, [[100, 1], 90], [10, 13], 8, 6])
      1
      >>> recursive_min([2, [[13, -7], 90], [1, 100], 8, 6])
      -7
      >>> recursive_min([[[-13, 7], 90], 2, [1, 100], 8, 6])
      -13
    """
    min = nested_num_list[0]
    while type(min) == type([]):
        min = min[0]
    for item in nested_num_list:
        if type(item) == type([]):
            min_of_elm = recursive_min(item)
            if min_of_elm < min:
                min = min_of_elm
        elif item < min:
            min = item
    return min

请注意，它不只是执行 recursive_min(item)，而是将其分配给一个变量，并将其与当前的 min 进行比较。我不明白为什么我需要这样做，因为在我看来，如果我在嵌入列表上执行整个函数，那是一个整数列表，那么它应该进入 elif 语句（而不是 if 语句) 并正确比较这些值。

我知道我必须在这里遗漏一些关于递归的东西。我非常感谢您能给我的任何见解，以帮助我了解是什么使第二个版本有效但第一个版本失败了。

谢谢！

4

2 回答 2

2

为什么它会起作用？您调用该函数，它会递归直到找到最小值。那么它有什么作用呢？它依次退出所有递归，直到回到顶层。那时， 的价值是min多少？正是在开始递归之前它是什么，因为您从未从递归函数中捕获返回值。

不要忘记函数的每次调用都有自己的局部变量，因此有自己的局部值min.

于 2012-05-15T18:41:51.237 回答
0

有很多方法可以解决这个问题。就个人而言，我更喜欢一种更实用的方法 - 仅使用列表上的递归，没有循环或局部变量。这当然不是解决问题的最有效方法，但它简单而优雅：

def recursive_min(num_list):
    return aux_min(num_list[1:], num_list[0]) if num_list else None

def aux_min(num_list, min_num):
    if not num_list:
        return min_num
    elif not isinstance(num_list, list):
        return min(num_list, min_num)
    else:
        return min(aux_min(num_list[0],  min_num),
                   aux_min(num_list[1:], min_num))

在上面的代码中， main 函数是recursive_min，它调用了 helper 函数aux_min。反过来，aux_min接收一个列表和当前最小值，并将问题拆分为三种情况：

  1. 如果列表为空，则返回当前最小值
  2. 如果是数字而不是列表，则返回数字与当前最小值之间的最小值
  3. 如果是列表，则递归返回其第一个元素与列表其余部分之间的最小值

它适用于列表列表，因为在第三种情况下，第一个元素可能是列表本身。

于 2012-05-15T19:17:57.450 回答