使用Python 3递归布尔检查，如果一个列表进行排序

我想写一个递归函数，它布尔检查，如果一个列表进行排序。如果列表排序，则返回true;如果未排序，则返回false。到目前为止，我想知道，如果我有“基本情况”正确（即，我的第一个“如果”语句）：使用Python 3递归布尔检查，如果一个列表进行排序

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

我是用我的初步if "L[i] > L[i + 1]:"的基本情况递归正确吗？

假设我的“基本情况”是正确的，我不知道如何递归确定名单在非降序排列。

来源

2012-07-23 captainHawk

这就是我将如何开始。写一个函数具有以下签名：

function isSorted(currentIndex, collection)

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

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

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

警告：这是一个可怕的使用递归

来源

2012-07-23 21:29:35 MStodd

感谢您的洞察力。我会尽力处理逻辑，看看我能想出什么。 – captainHawk 2012-07-24 17:05:55

没有，基本情况将是，当你到达列表的末尾，在这种情况下你会返回true。

否则，如果你正在寻找这两个元素是无序返回false。

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

来源

2012-07-23 21:58:52 UncleO

我同意@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-24 00:37:28 steveha

感谢您的洞察力。我会锤击整个过程并尝试将其应用于此问题。 – captainHawk 2012-07-24 17:03:20

DEF isSorted（检查表，I = 0）：如果I> = LEN（检查清单） - 1：返回true 否则：清单[I]> =清单[I + 1] 返回False isSorted（检查清单， i + 1） – captainHawk 2012-07-25 17:24:56

这就是我想出的答案，但事实证明，当它的假设为true时，返回true将不会打印。任何建议为什么它不是真实的？ – captainHawk 2012-07-25 17:26:48

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

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

return L[0] <= L[1] and isSorted(L[1:])

来源

2012-07-24 21:40:29 captainHawk

使用Python 3递归布尔检查，如果一个列表进行排序

回答

相关问题