Python 3.3：函数的递归版本

Question

Python 3.3：函数的递归版本

3

def abc(s):
    filter = [i for i in s.lower() if i in 'abcdefghijklmnopqrstuvwxyz']
    for i in range(len(filter) - 1):
        if filter[i] > filter[i+1]:
            return print(s, "is not abcdearian")
    return print(s,  "is abcdearian")


while True:
    try:
        s = input("String? ")
abc(s)

我在制作abc(s)的递归版本方面遇到了麻烦。有什么想法吗？

- Ace

递归不应该更像 def abc(s): ... abc(subs)... return 吗？具体来说，我是指递归需要在函数体内使用其他参数调用函数。 - Nisan.H

3个回答

0

尝试这段代码，它与问题中发布的代码等效，但是以递归方式编写：

from string import ascii_lowercase

def abc(s):
    f = [c for c in s.lower() if c in ascii_lowercase]
    if aux(f, 0):
        return s + " is abcdearian"
    else:
        return s + " is not abcdearian"

def aux(s, i):
    if i >= len(s)-1:
        return True
    elif s[i] > s[i+1]:
        return False
    else:
        return aux(s, i+1)

使用方式如下：

while True:
    s = input("String? ")
    if not s:
        break
    print(abc(s))

请注意，我将问题分为两部分：首先，“主”函数abc()负责过滤字符串，使用正确的初始值调用过程，并在最后返回结果字符串（或者你可以返回一个布尔值，在其他地方创建结果字符串）。

真正的工作是在辅助函数中完成的，它递归遍历字符串，检查字符串中所有相邻字符对是否符合“abcdearian”条件。 aux如何迭代字符串是有效的（抛开我们使用递归的事实），因为它从不使用s[1:]创建额外的中间字符串。这也是一个尾递归算法的示例，并且它紧密地反映了迭代解决方案的结构。

- Óscar López

@J.F.Sebastian 再想一想...为什么不等价？你能提供一个反例吗？ - Óscar López

Python 3.3 中没有小写字母。您可以使用 ascii_lowercase。此外，abc() 应返回布尔值以实现适当的关注点分离。 - jfs

非 ASCII 字母的代码点不一定按字母顺序排列（在 Python 3 中，str.isalpha() 操作 Unicode 字符串）。 - jfs

0

原始的最佳答案写法似乎过于复杂。我已经提交了一份编辑，希望能够解决这个问题。但是在我意识到这一点之前，我已经写了下面的答案和解释。为了方便其他人参考，我将保留它们：

def abc(s):
    filtered = [i for i in s.lower() if i in 'abcdefghijklmnopqrstuvwxyz']
    optionalNotString = ('' if _abc(filtered) else ' not')
    print( '{0} is{1} abcdearian'.format( repr(s), optionalNotString ) )

# Recursively process the "rest" (remainder) of the string.
# At each step, examine the first two characters.
def _abc(rest):
    if len(rest) < 2:
        # We've successfully compared all successive pairs, so return True.
        return True
    if (rest[0] > rest[1]):
        return False
    return _abc(rest[1:])

在使用中（测试最重要的情况，包括过短的字符串，并检测以字符串'acb'结尾的False条件，以及以字符串'bac'开头的False条件。我在第一次编写时遇到了一个错误，未能将'bac'识别为False！）：

abc( '' )
abc( 'a' )
abc( 'ac' )
abc( 'abc' )
abc( 'acb' )
abc( 'bac' )

输出：

'' is abcdearian
'a' is abcdearian
'ac' is abcdearian
'abc' is abcdearian
'acb' is not abcdearian
'bac' is not abcdearian

解释：

过滤只需要执行一次，因此在主要的“abc”函数中执行，而不是在递归的“_abc”函数中执行。
在每个步骤中，算法需要查看两个相邻的字符。在每次调用“_abc”时，这些将是前两个字符。
“_abc”需要处理两种情况：
- 情况1：字符串太短，无法进行比较。例如''或'a'。这样的字符串满足abcderian标准，因此返回True。
- 情况2：字符串至少为两个字符。执行前两个字符的abcderian计算。如果失败，则答案为False。否则，使用除第一个字符外的所有字符进行递归。
“repr（s）”是一种简单的方法，可以使“s”带有其周围的引号打印。
“optionalNotString”：True / False情况下所需的答案字符串仅通过存在/不存在' not'来区分。因此，使用“if .. else ..”表达式控制是否在格式化输出中包含' not'。当不需要时，替换为空字符串''。

- ToolmakerSteve

顺便说一句，我刚刚重新阅读了被接受的答案。我认为这有些过度，因为在“issorted（L）”中使用了zip。我认为它是作为答案的一部分，在迭代的每个步骤中被调用。该函数不应该成为解决方案代码的一部分；它展示了一种替代递归的方法。重新阅读他的解决方案，“issorted_recursive（L）”完成了所有工作，并以Pythonic的方式完成了工作。但是，如果解释对某人有用，我会把我的答案留在这里。 - ToolmakerSteve

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jfs · Accepted Answer

非递归解决方案：

def issorted(L):
    return all(x <= y for x, y in zip(L, L[1:]))

为了编写递归函数，您需要找到一种将问题拆分成较小或更简单的子问题的方法，这些子问题可以使用相同的方法解决：

#!/usr/bin/env python3
from string import ascii_lowercase

def abcdearian(s):
    return issorted_recursive([c for c in s.lower() if c in ascii_lowercase])

def issorted_recursive(L):
    return L[0] <= L[1] and issorted_recursive(L[1:]) if len(L) > 1 else True

这里的issorted_recursive()是一个递归函数。基本情况是当len(L) <= 1（一个零或一个元素的列表总是排序好的，因此在这种情况下返回True）。在递归情况下（len(L) > 1），如果第一项在已排序的顺序中（L[0] <= L[1]）且剩余部分的列表（L[1:]）也已排序，则认为列表L已排序。每次函数接收越来越小的输入，直到找到未排序的元素（L[0] > L[1]）或遇到基本情况并完成函数。

示例

while True:
    s = input("String? ")
    if not s:
        break
    print("{} is {}abcdearian".format(s, "" if abcdearian(s) else "not "))

输入

    abc
    bac

输出

String? abc is abcdearian
String? bac is not abcdearian
String?