Comment puis-je retourner les nombres impairs d'une liste, en utilisant seulement la récursivité en Python?

Question

Je ne veux pas utiliser while ou for loops, je veux juste utiliser récursion pour retourner les nombres impairs dans une liste donnée. Merci!

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

Aucune des variables supplémentaires ou des paramètres nécessaires.

Answer 2

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 

est ici une sortie de test de ce que je reçois quand je lance ce

[7, 5, 3, 1]

Answer 3

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 4

Voici une autre façon de le faire qui retourne la liste des nombres impairs plutôt que de modifier la liste transmise. Très similaire à celle fournie par GWW mais j'ai pensé que je l'ajouterais pour l'exhaustivité.

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

sortie est:

[1, 3, 5, 7, 9] 

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

Celui-ci évite les frais généraux de la copie de la liste, au prix d'obtenir la réponse en arrière et une grande augmentation du facteur de la laideur:

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

Compte tenu de la limite de profondeur de la pile par défaut de 1000 en python, je n'utiliserais vraiment pas la récursivité pour ça. Je sais qu'il ya beaucoup d'implémentations récursives ci-dessus est donc ici un non récurrent qui fait les choses comme python:

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

Et pour être complet; Si vraiment vous devez vraiment utiliser la récursivité, voici ce que je vais faire. Ceci est très similaire à la version par 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 

Cette version est beaucoup plus rapide car il évite de faire des copies de 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 [] 

Celui-ci utilise seulement O (log n) espace de pile

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

Eh bien, il sont un tas d'autres réponses, mais je pense que le mien est le plus propre:

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

Exercice amusant mais juste pour réitérer, ne le faites jamais récursivement dans la pratique.

Answer 10

bien puisque nous contribuons tous:

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

Comme il est parti, je ne pensais que je serais avec un carillon agréable, sensible, programmeur réel ^{solution TM}. Il est écrit en emacs et inspiré par la réponse de gnibbler.Comme le sien, il utilise &1 au lieu de % 2 (ajouter 2 dans co_consts est pure décadence si 1 est déjà là) et utilise cette astuce astucieuse pour obtenir le premier élément seulement si c'est impair, mais rase quelques cycles pour un gain de temps d'environ 5 % (sur ma machine, exécutant 2.6.5 compilé avec GCC 4.4.3 sur un noyau linux2).

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