如何在 Python 中仅使用递归返回列表的奇数？

Question

我不想使用 while 或 for 循环，只想使用递归返回给定列表中的奇数。谢谢！

Answer 1

def find_odds(numbers):
  if not numbers:
    return []
  if numbers[0] % 2 == 1:
    return [numbers[0]] + find_odds(numbers[1:])
  return find_odds(numbers[1:])

不需要额外的变量或参数。

Answer 2

def only_odd(L):
    return L[0:L[0]&1]+only_odd(L[1:]) if L else L

这个版本要快得多，因为它避免了复制 L

def only_odd_no_copy(L, i=0):
    return L[i:i+(L[i]&1)]+only_odd_no_copy(L, i+1) if i<len(L) else []

这个版本只使用 O(log n) 堆栈空间

def only_odd_logn(L):
    x=len(L)/2+1
    return L[:L[0]&1] + only_odd2(L[1:x]) + only_odd_logn(L[x:]) if L else L

Answer 3

def find_odds(numbers, odds):
    if len(numbers) == 0:
        return
    v = numbers.pop()
    if v % 2 == 1:
        odds.append(v)
    find_odds(numbers, odds)

odds = []
numbers = [1,2,3,4,5,6,7]
find_odds(numbers,odds)
# Now odds has the odd numbers
print odds

时得到的测试输出

这是运行[7, 5, 3, 1]

Answer 4

考虑到 python 中默认的堆栈深度限制为 1000，我真的不会为此使用递归。我知道上面有很多递归实现，所以这里有一个以 python 方式实现的非递归实现

print filter(lambda x: x % 2, range(0, 10))

：如果你真的必须使用递归，这是我的尝试。这与乔什·马修斯的版本非常相似。

def rec_foo(list):
    if not list:
        return []
    return ([list[0]] if list[0] % 2 else []) + rec_foo(list[1:])

print rec_foo(range(1, 10))

Answer 5

这是另一种方法，它返回奇数列表，而不是修改传入的列表。与 GWW 提供的非常相似，但我想为了完整性而添加它。

def find_odds(numbers, odds):
    if len(numbers) == 0:
        return odds

    if numbers[0] % 2 == 1:
        odds.append(numbers[0])

    return find_odds(numbers[1:],odds)

print find_odds([1,2,3,4,5,6,7,8,9],[])

输出是：

[1, 3, 5, 7, 9]

Answer 6

由于这是一个聚会，我只是想提出一个好的、合理的、真正的程序员^TM解决方案。它是用 emacs 编写的，灵感来自 gnibbler 的答案。与他一样，它使用 &1 而不是 % 2 （如果 1 已经存在，则将 2 添加到 co_consts 中是纯粹的颓废）并使用它仅当第一个元素奇数时才获取第一个元素的巧妙技巧，但减少了一些周期，节省了大约 5% 的时间（在我的机器上，在 linux2 内核上运行用 GCC 4.4.3 编译的 2.6.5）。

from opcode import opmap
import types

opcodes = [opmap['LOAD_FAST'],      0,0,   #    L
           opmap['JUMP_IF_FALSE'],  24,0, 
           opmap['DUP_TOP'],
           opmap['LOAD_CONST'],     0,0,   #    0
           opmap['BINARY_SUBSCR'],  
           opmap['LOAD_CONST'],     1,0,   #    1
           opmap['BINARY_AND'],
           opmap['SLICE+2'],
           opmap['LOAD_GLOBAL'],    0,0,   #    odds
           opmap['LOAD_FAST'],      0,0,
           opmap['LOAD_CONST'],     1,0,
           opmap['SLICE+1'],
           opmap['CALL_FUNCTION'],  1,0,
           opmap['BINARY_ADD'],
           opmap['RETURN_VALUE']]

code_str = ''.join(chr(byte) for byte in opcodes)

code = types.CodeType(1, 1, 4, 0x1 | 0x2 | 0x40, code_str, (0, 1),
                      ('odds',), ('L',), '<nowhere>', 'odds',
                      0, '')

odds = types.FunctionType(code, globals())

Answer 7

odds = []
def findOdds(listOfNumbers):
    if listOfNumbers[0] % 2 == 1:
        odds.append(listOfNumbers[0])
    if len(listOfNumbers) > 1:
        findOdds(listOfNumbers[1:])

findOdds(range(0,10))
print odds
# returns [1,3,5,7,9]

Answer 8

def odds(L):
    if L == []: 
        return []
    else:
        if L[0]%2:
            B = odds(L[1:])
            B.append(L[0])
            return B
        else:
            return odds(L[1:])

Answer 9

>>> def fodds(alist, odds=None):
...     if odds is None: odds = []
...     if not alist: return odds
...     x = alist[0] # doesn't destroy the input sequence
...     if x % 2: odds.append(x)
...     return fodds(alist[1:], odds)
...
>>> fodds(range(10)) # only one arg needs to be supplied
[1, 3, 5, 7, 9] # same order as input
>>>

这避免了列表复制开销，但代价是向后获得答案并大幅增加丑陋因素：

>>> def fo(aseq, pos=None, odds=None):
...     if odds is None: odds = []
...     if pos is None: pos = len(aseq) - 1
...     if pos < 0: return odds
...     x = aseq[pos]
...     if x % 2: odds.append(x)
...     return fo(aseq, pos - 1, odds)
...
>>> fo(range(10))
[9, 7, 5, 3, 1]
>>>

Answer 10

好吧，因为我们都在做出贡献：

def odds(aList):
    from operator import lshift as l
    if aList and not aList[1:]:
        return aList if aList[-1] - l(aList[0]>>1, 1) else list()
    return odds(aList[:len(aList)/3+1]) + odds(aList                                     \
    [len(aList)/3+1:]) if aList else []

Answer 11

好吧，还有很多其他答案，但我认为我的答案是最干净的：

def odds(L):
   if not L: 
      return []
   return [L[0]] * (L[0] % 2) + odds(L[1:])

有趣的练习，但只是重申一下，在实践中永远不要递归地执行此操作。