0

我正在尝试编写一个递归函数来执行布尔检查列表是否已排序。如果列表已排序，则返回 true；如果未排序，则返回 false。到目前为止，我试图了解我的“基本情况”是否正确（即我的第一个“if”语句）：

def isSorted(L, i=[]):
    if L[i] > L[i + 1]:
         return false
    else:
         return true

我的初始if "L[i] > L[i + 1]:"作为递归的基本情况是否正确？

假设我的“基本情况”是正确的，我不确定如何递归地确定列表是否按非降序排序。

4

4 回答 4

1

这是我想出的。我将默认列表指定为0; 首先检查第一项是否是最后一项。如果没有，应该检查每个项目，直到它到达列表的末尾。

def isSorted(L):
    # Base case
    if len(L) == 1:
        return True

return L[0] <= L[1] and isSorted(L[1:])
于 2012-07-24T21:40:29.000 回答
0

这就是我要开始的方式。编写一个具有以下签名的函数：

function isSorted(currentIndex, collection)

在函数内部，检查是否currentIndex在集合的末尾。如果是，则返回 true。

collection[index]接下来，检查是否collection[index+1]正确排序。

如果不是，则返回 false
如果是，则返回isSorted(currentIndex+1, collection)

警告：这是递归的可怕用途

于 2012-07-23T21:29:35.840 回答
0

我同意@MStodd：递归不是在 Python 中解决这个问题的方法。对于很长的列表，Python 可能会溢出它的堆栈！但是对于短名单应该没问题，如果你的老师给你这个问题，你需要这样做。

以下是您应该如何考虑这个问题。每次递归调用你应该做以下三件事之一： 0）返回False，因为你发现列表没有排序；1）True因为您已达到基本情况而返回；2）分解工作并以某种方式使剩余的问题更小，直到达到基本情况。基本情况是不能进一步分解工作的情况。

这是一个大致的轮廓：

def recursive_check(lst, i):
    # check at the current position "i" in list
    # if check at current position fails, return False
    # update current position i
    # if i is at the end of the string, and we cannot move it any more, we are done checking; return true
    # else, if i is not at the end of the string yet, return the value returned by a recursive call to this function

例如，这是一个检查字符串中是否有字符的函数'@'。如果字符串True中没有任何地方，它应该返回。@

def at_check(s, i):
    if s[i] == '@':
        return False
    i += 1
    if i >= len(s):
        return True
    else:
        return at_check(s, i)

我写了上面的大纲，就像我上面给出的大纲一样。这是一个稍短的版本，它做同样的事情，但顺序不完全相同。

def at_check(s, i=0):
    if i >= len(s):
        return True
    if s[i] == '@':
        return False
    return at_check(s, i+1)

编辑：请注意，我将i=0论点放入at_check(). 这意味着“默认”值i将是 0。调用此函数的人可以直接调用at_check(some_string)，而不是在第一次调用时显式传入 0；默认参数将提供第一个 0 参数。

我们真正需要添加一个的唯一时间i是当我们递归调用该函数时。我们加 1 的部分是重要的“分解工作”部分。我们尚未检查的字符串部分是 之后的部分i，每次调用该部分都会变小。我不知道你是否已经了解了“切片”，但我们可以使用“切片”来让字符串在每次调用时变得越来越小。这是一个以这种方式工作的版本；如果您还不知道切片，请忽略它。

def at_check(s):
    if s == '':  # empty string
        return True
    if s[-1] == '@':  # is last character '@'?
        return False
    return at_check(s[:-1]) # recursive call with string shortened by 1

在这个版本中，空字符串是基本情况。空字符串不包含@，所以我们返回True。然后如果最后一个字符是@我们可以返回False; 但否则我们砍掉最后一个字符并递归调用该函数。在这里，我们通过使字符串越来越短直到我们完成来分解工作。但是将 1 添加到索引变量，并在字符串中移动索引，将是同一件事。

研究这些示例，直到您了解使用递归来分解工作并在每个递归调用上取得一些进展。然后看看你是否能弄清楚如何将这个想法应用到查找列表是否排序的问题上。

祝你好运！

于 2012-07-24T00:37:28.750 回答
0

不，基本情况将是当您到达列表末尾时，在这种情况下您返回 true。

否则，如果您正在查看的两个元素乱序返回 false。

否则，返回列表中下一个元素的递归调用结果。

于 2012-07-23T21:58:52.430 回答