es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Python excede el límite de recursión.

25 Jul, 2023 Programación

Estoy tratando de desarrollar un algoritmo de ordenación por mezcla utilizando la estrategia “divide y vencerás”. Sin embargo, durante la parte de división, estoy obteniendo un error recursivo que indica que he excedido la recursión. Esto es lo que tengo:

c = [3,5,4,2,1,6,7]
def mergesort(nums):
    if len(nums) == 1:
        return
    n = len(nums)//2
    a = c[:n]
    b = c [n:]
    mergesort(a)
    mergesort(b)
    i = 0
    j = 0
    k = 0

mergesort(c)
Tags:  , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    El problema con el código proporcionado es que en la función mergesort, se verifica que el parámetro nums tenga una longitud de 1, pero el código continúa dividiendo c en a y b sin utilizar el parámetro nums. En su lugar, se está utilizando directamente la lista c, lo que causa una recursión infinita. Para solucionar este problema, la función de ordenación por mezcla debería utilizar el parámetro nums de entrada en lugar de la lista c codificada:

    def mergesort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums)//2
    left = mergesort(nums[:mid])
    right = mergesort(nums[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

    En esta función de ordenación por mezcla actualizada, se verifica que el parámetro nums de entrada tenga una longitud de 1, y si es así, se devuelve tal cual. Luego, la función divide la lista de entrada nums en dos mitades, left y right, y aplica de forma recursiva la función mergesort a cada una de ellas. Finalmente, se llama a la función merge para combinar las mitades left y right ordenadas en una única lista ordenada, que es devuelta por la función mergesort.

    Al utilizar este enfoque, se debería resolver el problema de la recursión infinita, y el algoritmo de ordenación por mezcla debería ser capaz de ordenar correctamente la lista de entrada.

Comments are closed.