Como posso retornar um único valor booleano de uma função recursiva? - python, recursão

Eu tenho essa função:

def most(P, S):
def recursion(P,S):
if len(S) == 0:
return []
elif P(S[0]):
return [P(S[0])] + recursion(P, S[1:])
else:
return recursion(P, S[1:])
if len(recursion(P,S)) > len(S)/2:
return True
else:
return False

Leva uma entrada de função, P e lista, S. Se o resultado de P (S [i]) for verdadeiro para a maioria de S, então a função most () deve retornar true. Alguma idéia de como eu posso fazer isso recursivamente sem uma função dentro de uma função? Em outras palavras, como posso retornar um único valor booleano de uma função recursiva que recebe uma lista como sua entrada?

Obrigado!

Respostas:

A maior chave para a recursão é entender a "condição terminal". Qual é o estado em que a função deve parar? Neste caso, é a lista vazia.

def most(pred, lst):
if lst == []:
return # but what do we return?

Você precisará acompanhar o número da listaelementos que atendem a uma expectativa ... então você tem que acompanhar tanto a expectativa (ou seja, quantos devem ser verdadeiros para que "a maioria" seja verdadeira), assim como a contagem até o momento. Vamos adicionar aqueles ...

def most(pred, lst, threshold=None, count=0):
if threshold is None:
threshold = len(lst) // 2

if lst == []:
return count > threshold

Então, precisamos "desconstruir" a lista para poder recorrer a ela. Vamos adicionar isso ...

def most(pred, lst, threshold=None, count=0):
if threshold is None:
threshold = len(lst) // 2

if lst == []:
return count > threshold

# Check the "truth" of the head of the list...
if pred(lst[0]):
count += 1

# ...and pass the tail of the list into the next iteration.
return most(pred, lst[1:], threshold, count)

Isso deve ser tudo o que você precisa. Agora, vou avisá-lo de que, se as suas listas forem de tamanho significativo, o Python expandirá sua pilha. Isso também é significativamente mais lento do que uma solução usando um for loop ou reduce, por causa de todas as chamadas de função adicionais.

Se eu estivesse implementando most para o código de produção, eu faria isso:

def most(pred, lst):
return sum(1 for x in lst if pred(x)) > len(lst) // 2