El problema:

Cuente el número de elementos en una Lista usando recursividad .

Escribí la siguiente función:


def count_rec(arr, i):
    """
        This function takes List (arr) and Index Number
        then returns the count of number of elements in it 
        using Recursion.
    """
    try:
        temp = arr[i]  # if element exists at i, continue
        return 1 + count_rec(arr, i+1)
    except IndexError:
        # if index error, that means, i == length of list
        return 0

Noté algunos problemas con esto:

  1. RecursionError (cuando el número de elementos es más de 990)
  2. Usando un elemento temp (¿desperdiciando memoria ...?)
  3. Exception Manejo (siento que no deberíamos usarlo a menos que sea necesario)

Si alguien puede sugerir cómo mejorar la solución anterior o encontrar una alternativa , sería realmente útil.

1
Gagan Deep Singh 29 may. 2020 a las 00:01

3 respuestas

La mejor respuesta

Lo que tiene es probablemente tan eficiente como lo que obtendrá para este experimento mental (obviamente, python ya calcula y almacena la longitud de los objetos LIST, que se pueden recuperar con el len () incorporado, por lo que esta función es completamente innecesaria) .

Puede obtener un código más corto si desea:

def count(L):
    return count(L[:-1])+1 if L else 0

Pero aún necesita cambiar el límite de recursión de Python.

import sys; sys.setrecursionlimit(100000)

Sin embargo, debemos tener en cuenta que en la mayoría de los casos, las declaraciones "if else" tardan más en procesarse que "try except". Por lo tanto, "intentar excepto" va a ser mejor (si buscas rendimiento). Por supuesto, es extraño hablar de rendimiento porque la recursividad generalmente no funciona muy bien, debido a cómo Python administra los espacios de nombres y demás. La recursión es típicamente mal vista, innecesaria y lenta. Por lo tanto, tratar de optimizar el rendimiento de recursión es un poco más extraño.

Un último punto a tener en cuenta. Usted menciona que temp = arr [i] ocupa memoria. Sí, posiblemente unos pocos bytes. Por supuesto, cualquier cálculo que haga para determinar si arr tiene un elemento en i, tomará unos pocos bytes en la memoria, incluso simplemente ejecutando "arr [i]" sin asignación. Además, esos bytes se liberan en el segundo en que la variable temporal cae fuera del alcance, se reutiliza o la función sale. Por lo tanto, a menos que esté planeando lanzar 10,000,000,000 de subprocesos, asegúrese de que no haya una degradación del rendimiento al usar una variable temporal como esa.

1
Bobby Ocean 28 may. 2020 a las 22:57

Puedes usar pop () para hacerlo.

def count_r(l):
    if l==[]:
        return 0
    else:
        l.pop()
        return count_r(l)+1
1
maede rayati 28 may. 2020 a las 21:48

Estás buscando algo como esto

def count_rec(arr):
    if arr == []:
        return 0
    return count_rec(arr[1:]) + 1
1
HackLab 28 may. 2020 a las 21:07