Python: función recursiva para encontrar el número más grande en la lista

Estoy tratando de hacer un trabajo de laboratorio del libro de texto Zelle Python Programming

La pregunta me pidió “escribir y probar una función recursiva max() para encontrar el número más grande en una lista. El máximo es el mayor del primer elemento y el máximo de todos los demás elementos”. No entiendo muy bien la pregunta del libro de texto.

 def Max(list): if len(list)  list[0] else list[0] def main(): list = eval(raw_input(" please enter a list of numbers: ")) print("the largest number is: ", Max(list)) main() 

¿O tal vez se supone que debo abrir un archivo de texto con números y luego usar recursivo?

Creo obras recursivas como esta.

 def function() > if something: >>return 0 >else: >>return function() 

Su comprensión de cómo funciona la recursión parece estar bien.

Su if-block está desordenado, tiene dos s de uno en uno if la alineación está fuera. Debes eliminar tu primera else y eliminar la sangría de todo lo que esté por debajo de un solo nivel. p.ej:

 def Max(list): if len(list) == 1: return list[0] else: m = Max(list[1:]) return m if m > list[0] else list[0] def main(): list = eval(raw_input(" please enter a list of numbers: ")) print("the largest number is: ", Max(list)) main() 

Aquí hay un enfoque más para resolver el problema anterior.

 def maximum(L): if len(L) == 1: return L[0] else: return max(L[0],maximum(L[1:])) 

así ejemplo de entrada y salida:

 L= [2,4,6,23,1,46] print maximum(L) 

produce

 46 

El enfoque básico es este.

  1. Si la lista contiene un solo elemento, ese elemento es el máximo. Devuélvalo inmediatamente.
  2. De lo contrario, la lista contiene múltiples elementos. O el primer elemento de la lista es el máximo, o no lo es.
  3. El máximo del primer elemento es simplemente el primer elemento de la lista.
  4. Llame recursivamente a Max en el rest (todos menos el primer elemento) para encontrar el máximo de esos elementos.
  5. Compara los resultados del paso 3 y 4. El resultado es el número que es mayor. Devolverlo.

Ahora mismo tienes algunos errores de syntax. Por ejemplo, tiene dos cláusulas else para un solo if , y la sangría parece graciosa. Solo puedes tener uno else para un bloque if . Pero si sigue estas instrucciones, debe tener un algoritmo de trabajo.

Publico un enfoque de solución diferente del problema. La mayoría de las respuestas manipulan la lista utilizando el operador de división en cada llamada recursiva. Cuando el ejercicio no proporciona un prototipo de función estricta para usar, también paso como parámetro de función la longitud de la lista.

Supongamos que intentamos encontrar y devolver el elemento máximo de una secuencia S , de n elementos.

Prototipo de función: Max(S, n)

Caso base: Si S contiene solo un artículo, devuélvalo. (Obviamente, el único elemento en la secuencia es el máximo).

Repetir: si no es el caso base, llame a Max cada vez para obtener un elemento menos, es decir, llame a Max(S, n-1) . Luego almacenamos el valor de retorno en una variable llamada previous que indica el elemento anterior de la secuencia y verificamos ese valor con el siguiente elemento de la secuencia, que es el elemento más a la derecha en la llamada recursiva actual, y devolvemos el máximo de estos valores .

En la siguiente figura se proporciona una traza de recursión del procedimiento anterior. Supongamos que tratamos de encontrar el máximo de una lista que contiene [5, 10, 20, 11, 3] .

Traza de recursion

Nota: Para ayudarlo más, tenga en cuenta que recursivamente iteramos la lista desde el elemento más a la derecha hasta el más a la izquierda.

Finalmente aquí está el código de trabajo:

 def find_max_recursively(S, n): """Find the maximum element in a sequence S, of n elements.""" if n == 1: # reached the left most item return S[n-1] else: previous = find_max_recursively(S, n-1) current = S[n-1] if previous > current: return previous else: return current if __name__ == '__main__': print(find_max_recursively([5, 10, 20, 11, 3], 5)) 

Nota: la implementación recursiva funcionará por defecto solo con secuencias de 1000 elementos más.

Para combatir contra las recursiones infinitas, los diseñadores de Python tomaron la decisión intencional de limitar el número total de activaciones de funciones que pueden estar activas simultáneamente. El valor preciso de este límite depende de la distribución de Python, pero un valor predeterminado típico es 1000 . Si se alcanza este límite, el intérprete de Python genera un RuntimeError con un mensaje, se maximum recursion depth exceeded .

Michael T. Goodrich (2013), Estructuras de datos y algoritmos en Python , Wiley

Para cambiar el valor predeterminado haz:

 import sys sys.setrecursionlimit(1000000) 
 def Max(lis,maxx=-float("inf")): if len(lis) == 1: #only one element in lis return maxx if maxx>lis[0] else lis[0] #return lis[0] if it's greater than maxx else: m=lis[0] if lis[0]>maxx else maxx # m = max(lis[0],maxx) return Max(lis[1:],m) #call Max with lis[1:] and pass 'm' too print Max([1,2,39,4,5,6,7,8]) #prints 39 print Max([1,2,3,4,5,6,7,8]) #prints 8 

Estas soluciones fallan después de cierto tamaño de lista.

Esta es una versión mejor:

 def maximum2(a, n): if n == 1: return a[0] x = maximum2(a[n//2:], n - n//2) return x if x > a[0] else a[0] def maximum(a): return maximum2(a, len(a)) maximum(range(99999)) >>> 99998 

Una forma simple sería ordenar la lista primero y luego usar la indexación.

Aquí hay una función que funcionaría:

 a = [1,233,12,34] def find_max(a): return sorted(a)[-1] 
 def getMaxNumber(numbers): return 'NA' if len(numbers) == 0 else max(numbers)