How can I return the odd numbers of a list, using only recursion in Python?

Question

I do not want to use while or for loops, just want to use recursion to return the odd numbers in a given list. Thanks!

Answer 1

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

Here's a test output of what I get when I run this

[7, 5, 3, 1]

Answer 2

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 3

Here's another way of doing it which returns the list of odd numbers rather than modifying the list passed in. Very similar to that provided by GWW but I thought I'd add it for completeness.

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

Output is:

[1, 3, 5, 7, 9]

Answer 4

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

No extra variables or parameters needed.

Answer 5

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

This one avoids the list copying overhead, at the cost of getting the answer backwards and a big increase in the ugliness factor:

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

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 7

Considering the default stack depth limit of 1000 in python, I would really not use recursion for this. I know there are a lot of recursive implementations above so here's a non-recursive one that is doing it the python way:

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

And for the sake of completeness; if you really really must use recursion here's my go at it. This is very similar to the version by Josh Matthews.

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 8

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

This version is much faster as it avoids making copies of 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 []

This one only uses O(log n) stack space

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 9

Well, there are a bunch of other answers but I think mine's the cleanest:

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

Fun exercise but just to reiterate, don't ever do this recursively in practice.

Answer 10

well since we're all contributing:

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

Since it's a party, I just thought I'd chime in with a nice, sensible, Real Programmer^TM solution. It's written in emacs and inspired by gnibbler's answer. Like his, it uses &1 instead of % 2 (adding 2 into co_consts is pure decadence if 1 is already there) and uses that nifty trick for getting the first element only if it's odd, but shaves some cycles off for a time savings of around 5% (on my machine, running 2.6.5 compiled with GCC 4.4.3 on a linux2 kernel).

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())