如何返回列表的奇数,在Python中只使用递归?[关闭]

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:])

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

def only_odd(L):
    return L[0:L[0]&1]+only_odd(L[1:]) if L else 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(logn)堆栈空间

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

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]

考虑到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))

这是另一种方法,它返回奇数列表,而不是修改传入的列表。非常类似于 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]

既然是派对,我就想找一个好的,明智的,真正的程序员 ^商标 解决方案。它是用emacs写成的,灵感来自gnibbler的答案。就像他的,它用 &1 而不是 % 2 (将2添加到 co_consts 如果1已经存在,那就是纯粹的颓废(decadence)),并且仅当第一个元素是奇数时才使用这个漂亮的技巧来获取它,但是会减少一些周期,节省大约5%的时间(在我的机器上,在linux2内核上运行用GCC4.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())

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]

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:])

>>> 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]
>>>

既然我们都有贡献:

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 []

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

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