¿Cómo mantener el recuento en una función recursiva? [python]

Question

Escribí una función recursiva para encontrar el no. de instancias de una subcadena en la cadena primaria. La forma en que estoy contando es declarando/inicializando el recuento como una variable global fuera del alcance de la función. El problema es que me dará resultados correctos solo la primera vez que se ejecuta la función, porque después de eso cuenta! = 0 para empezar. Y si lo tengo dentro de la función, que cada vez que se llama de forma recursiva, que va a ser ajustado a 0.

count=0 
def countSubStringMatchRecursive(target,key): 
    index=find(target,key) 
    global count 
    targetstring=target 
    if index>=0: 
     count=count+1 
     target=target[index+len(key):] 
     countSubStringMatchRecursive(target,key) 
    else : 
     pass 
    return "No. of instances of", key, 'in', targetstring, 'is', count 

Nota: Estoy buscando la solución para una función específica recursive, tengo un proceso iterativo función que funciona bien.

EDIT: Gracias a todos, esto era parte de la tarea, por lo que sólo estaba usando el módulo string

Answer 1

Una forma de modificar el código sería el uso de una función local de la siguiente manera:

def countSubStringMatchRecursive(target,key): 
    def countit(target,key,count): 
     index=find(target,key) 
     if index>=0: 
      target=target[index+len(key):] 
      count += countit(target,key,count) + 1 
     return count 
    return "No. of instances of", key, 'in', target, 'is', countit(target,key,0) 

Answer 2

Otra forma podría ser tener un tercer parámetro opcional en la función countSubStringMatchRecursive llamada recuento que originalmente se configuró en 0. De esa forma podrías hacer un seguimiento del conteo. Esto expondría la variable de conteo al mundo exterior que podría no ser deseable, pero como no es peor que su variable global, no creo que sea un problema en su caso.

También tendría que cambiar el código para hacer que la última llamada recursiva sea la llamada que da la declaración de devolución al mundo exterior. Vea este ejemplo (no probado):

def countSubStringMatchRecursive(target, key, count = 0): 
    index = find(target, key) 
    targetstring = target 
    if index >= 0: 
     count += 1 
     target = target[index+len(key):] 
     countSubStringMatchRecursive(target, key, count) 
    else: 
     return "No. of instances of", key, 'in', targetstring, 'is', count 

Editar: me di cuenta de que usted necesita un cuarto parámetro a ser capaz de mantener la cadena original que viaja a lo largo de la recursividad. Esta es probablemente una solución menos que óptima y recomendaría usar la solución de Greg Hewgill. Tiene una separación clara entre las interacciones con el exterior y la "lógica de negocios", haciendo que el código sea más reutilizable.

Answer 3

Su función recursiva tiene un rendimiento O (n^2) porque copia el contenido restante de la cadena cada vez que encuentra una coincidencia. Esto es más lento que la solución iterativa O (n) e innecesariamente.

puede volver a escribir fácilmente para ser más rápido, y al mismo tiempo simplificar el código y ampliar su funcionalidad pasar un índice de inicio de la búsqueda como un parámetro opcional para la función:

def countSubStringMatchRecursive(target, key, start_index = 0): 
    index = target.find(key, start_index) 
    if index >= 0: 
     return countSubStringMatchRecursive(target, key, index + len(key)) + 1 
    return 0 

target_string = 'an apple and a banana' 
key = 'an' 
count = countSubStringMatchRecursive(target_string, key) 
print "Number of instances of %r in %r is %d" % (key, target_string, count) 

de salida:

Number of instances of 'an' in 'an apple and a banana' is 4 

actualización: Si realmente desea usar función de búsqueda del módulo de cadena, puede hacer esto con sólo cambiar una sola línea:

index = find(target, key, start_index) 

Answer 4

¿Qué tal esto?

def count_it(target, key): 
    index = target.find(key) 
    if index >= 0: 
     return 1 + count_it(target[index+len(key):], key) 
    else: 
     return 0 


print count_it("aaa bbb aaa ccc aaa", "aaa") 

Salida:

3 

Answer 5

Esto es algo similar a la respuesta de Greg Hewgill. Sin embargo, en su lugar pasamos el conteo actual cada vez que llamamos a la función, y luego devolvemos el conteo cuando ya no hay más coincidencias.Si bien sospecho que no hay diferencia en Python, en los idiomas que implementan la recursividad de la cola de espera, esto permite optimizar cada llamada sucesiva a do_count en la pila de llamadas. Esto significa que cada llamada a do_count no hace que crezca la pila de llamadas.

def count_sub_strings(target, key): 
    def do_count(target, key, count): 
     index = target.find(key) 
     if index >= 0: 
      target = target[index + len(key):] 
      return do_count(target, key, count + 1) 
     else: 
      return count 
    return "No. of instances of %s in %s is %s" % (key, target, do_count(target, key, 0)) 

Answer 6

No no probado ...

código:

def countSubStringMatchRecursive(target, key, count=0): 
    #### index = find(target, key) # HUH? 
    index = target.find(key) 
    if index >= 0: 
     count += 1 
     target = target[index+len(key):] 
     count = countSubStringMatchRecursive(target, key, count) 
    return count 

for test in ['', 'bar', 'foo', 'foofoo', 'foo foo foo fo']: 
    print countSubStringMatchRecursive(test, 'foo'), test.count(key), repr(test) 

de salida:

0 0 '' 
0 0 'bar' 
1 1 'foo' 
2 2 'foofoo' 
3 3 'foo foo foo fo' 

Estoy suponiendo que esto es sólo diversión o tarea ... la función recursiva debe ser más lenta que la correspondiente solución iterativa de Python, que será b e naturalmente lento que el uso target.count(key) ... así que no he molestado con la fijación de todos los problemas que su versión tenía ... pero leer PEP-008 :-)

Comentarios en módulo string

Usted comentó que había omitido from string import find. ¿Qué versión de Python estás usando? ¿Cuál es la última fecha de actualización en el libro o tutorial que estás usando?

Desde el inicio del módulo string (que habrá en el equipo como <your Python install directory>/Lib/string.py; estoy citando de la versión 2.6):

"" "Una colección de las operaciones de cadena (la mayoría ya no se utilizan) .

Advertencia:.. la mayor parte del código que ves aquí no se utiliza normalmente en la actualidad a partir de Python 1.6, muchas de estas funciones se implementan como métodos en el objeto de cadena estándar de lo que solían ser implementado por un módulo integrado llamado strop, pero strop ahora está obsoleto.

etc """

y aquí está el código de ese archivo para la función find (despojado de comentarios):

def find(s, *args): 
    return s.find(*args) 

por lo que usar string.find(target, key) en lugar de target.find(key) es un desperdicio.

Answer 7

Una nota al margen: todas las soluciones presentadas (desde la Q original a todas las As) resuelven un problema diferente al especificado (imagino que es un error en el enunciado específico del problema, pero vale la pena asi que;-). Considere:

>>> 'banana'.count('ana') 
1 
>>> sum('banana'[x:x+3]=='ana' for x in range(len('banana'))) 
2 

la primera expresión está contando la que no se solapan ocurrencias de 'ana' en 'banana'; el segundo está contando todas las ocurrencias - hay dos ocurrencias en total, en los índices 1 y 3 en 'banana', y se superponen. Así que, dado el enunciado del problema, y ​​cito:

busque el no. de instancias de una subcadena en la cadena principal.

sin ninguna mención de "no se solapan", parece que la superposición de las ocurrencias deben ser contados. Por supuesto, eso es fácil de solucionar, una vez que se advierta, solo tiene que avanzar en 1 cada vez, en lugar de avanzar en len(key), lo que le permite omitir las repeticiones superpuestas.

Así, por ejemplo:

import string 

def countit(target, key, startfrom=0): 
    where = string.find(target, key, startfrom) 
    if where < 0: return 0 
    return 1 + countit(target, key, where+1) 

print countit('banana', 'ana') 

impresiones 2, contando ambas ocurrencias (superposición).

Answer 8

def countSubStringMatchRecursive(target,key): 
index = string.find(target, key) 
if index == -1: 
    return 0 
else: 
    return 1 + countSubStringMatchRecursive(target[index+len(key):],key) 

Answer 9

Estoy haciendo este curso en OpenCourseware, es genial. De todos modos, esto es lo que hice. Me inspiré en Adamse arriba.

def countSubStringMatchRecursive(target, key, counter = 0): 
    if find(target,key) == 0: 
     countSubStringMatchRecursive(target[1:], key, counter + 1) 
    elif find(target,key) > 0: 
     countSubStringMatchRecursive(target[1:], key, counter) 
    elif find(target,key) == -1: 
     print counter 

Answer 10

Teniendo en cuenta la superposición de las ocurrencias y el mantenimiento de la definición original de MIT este es el código más simple y más compacto que pueda conseguir.

código:

from string import * 
def countSubStringMatchRecursive(target, key): 
    index = find(target, key) 
    if index > -1: 
     return countSubStringMatchRecursive(target[index + 1:], key) + 1 
    return 0 


def test(target, key): 
    instances = countSubStringMatchRecursive(target, key) 
    if instances == 0: 
     print "No instance of %r in %r" % (key, target) 
    else: 
     print "Number of instances of %r in %r: %d" % (key, target, instances) 

test("atgacatgcacaagtatgcat","ggcc") 
test("atgacatgcacaagtatgcat","atgc") 
test("banana", "ana") 

salida:

No instancia de 'CCGG' en 'atgacatgcacaagtatgcat'

Número de casos de 'ATGC' en 'atgacatgcacaagtatgcat': 2

Número de instancias de 'ana' en 'banana': 2