1

Tengo el siguiente programa el cual debe determinar RECURSIVAMENTE si dos listas son SIMETRICAS o no, devolviendo True o False respectivamente. Para ello he desarrollado el siguiente codigo, que en la ejcucion me retorna correctamente. Una lista es simetrica si al recorrer los elementos de izquierda a derecha se obtienen los mismos elementos que al recorrerla de derecha a izquierda. La FUNCION DEBE SER RECURSIVA

import archive

l1 = [124, 87, 25, 01, 31, 65]
l2 = [15, 22, 55, 22, 15]
print(l1)
print(l2)


def functions(l1):
    if l1[0:] == l1[:5]:
        return True
    else:
        return False

-----ACTUALIZACIÓN DE CÓDIGO-----

def is_sym(l1):        
    if len(l1) == 1:    
        return True     
    elif len(l1) == 2:
        if l1[0] == l1[-1]:
            return True
    else:
        len(l1) != 1 and len(l1) != 2
        if l1[0] == l1[-1]:
            return True
        else:
            return False

LOS PROBLEMAS VIENEN EN LA LLAMADA A LA FUNCIÓN, QUE NO SE DÓNDE DEBO REALIZAR DICHA LLAMADA

2 respuestas 2

0

Ya que se trata de una tarea académica, no está bien que te de la solución, pero si es correcto que te ayude a encontrarla.

La forma de abordar la recursividad es imaginar que ya tienes hecha una función que te resuelve el problema, pero para una lista más pequeña que la que tú tienes, y pensar cómo te aprovecharías de esa función para resolver tu caso.

Es decir, imagina que tienes una lista de 10 elementos: [1,2,3,4,5,5,4,3,2,1] y necesitas saber si esa lista es simétrica. E imagina que ya tienes hecha una función, digamos simetrica8(), que funciona para listas de 8 elementos y te dice si la lista de 8 elementos es simétrica o no. ¿Cómo usarías esa información?

La idea es: miro el primer y último elemento de mi lista (o sea lista[0] y lista[-1], pues supongo que sabrás que el índice -1 significa el último). Si son distintos, ya sé que la lista no es capicúa. Si son iguales, llamo a simetrica8() pasándole mi lista, excepto el primer y último elemento, así: simetrica8(lista[1:-1]). Si el resultado de esto es True, es que la lista entera era simétrica y si es False, que no.

Claro... si tan sólo tuvieramos esa función "mágica" que funciona para 8 elementos... ¡Pero lo asombroso de la recursividad es que la tenemos! Se trata de la misma función que estás escribiendo. Sólo queda programarle lo que se llama "el caso trivial", que es el más pequeño que puedas imaginar y que sepas resolver.

El caso trivial es del de una lista de longitud 1 ó 2. Una lista como [5] es simétrica siempre por definición (ya que tiene un solo elemento por tanto el primero y el último son el mismo). Una lista como [2,2] es simétrica si el primero y último coinciden.

Entonces la estructura general de una función recursiva es:

  1. Mirar si el parámetro corresponde al caso "trivial" y en ese caso retornar la respuesta adecuada.
  2. Si no, calcular la respuesta correcta usando parte de tus datos, y llamando a tí misma con los datos restantes.
  3. Retornar la respuesta correcta

Ya que cada llamada a sí misma usa menos datos, llegará un momento que alcanzará el caso trivial y a partir de ahí la respuesta se va "propagando hacia arriba" hasta que la función de arriba del todo retorne el resultado correcto.

Adaptando este esquema general a tu caso (pero en pseudocódigo por no darte la solución completa) sería:

def simetrica(lista):
   Si la lista es de tamaño 1 o 2
       retornar si lista[0] == lista[-1]
   En caso contrario
       si lista[0] != lista[-1] retornar False
       si no, retornar lo que devuelva simetrica(lista[1:-1])
4
  • Muchisimas gracias por su tiempo y dedicacion. Su comentario me ha servido de gran ayuda para poder entender la recursividad y abordar los problemas de dicho tipo
    – Matilde
    Commented el 26 nov. 2019 a las 18:13
  • Para terminar de entender el funcionamiento de la recursion, cuando retornamos lo siguiente: return is_sym(arr[1:-1]) ¿estamos recorriendo la lista desde la posicion 1 hasta el ultimo elemento situado en la posicion -1?
    – Matilde
    Commented el 27 nov. 2019 a las 16:06
  • @Matilde la expresión arr[1:-1] es un caso de lo que en python se llama un slice, que se puede traducir por rodaja y que permite tomar de la lista arr un subconjunto de elementos. En general arr[inicio:fin] extrae sólo los elementos comprendidos entre el índice inicio y el anterior a fin. En el caso [1:-1] va del elemento de índice 1 hasta el anterior al -1. O sea, es la lista excepto el elemento 0 (el primero) y el -1 (el último). Esa lista se le pasa a is_sym() para que nos diga si es simétrica. El resultado (True o False) sería lo que retornamos.
    – abulafia
    Commented el 28 nov. 2019 a las 8:07
  • Observa que return is_sym(arr[1:-1]) no "recorre" nada en realidad. Sólo crea una lista más pequeña que la incial (pues le faltan los elementos primero y último) y averigua si esa lista es o no simétrica, pero no recorriéndola, sino preguntándoselo a is_sym() para que se lo diga. Esta función (ya que es ella misma), hará lo mismo, reduciendo de nuevo la lista y volviendo a preguntar a is_sym(). Así hasta que la lista tenga sólo 1 ó 2 elementos en cuyo caso ya puede responder directamente (y la respuesta se "propaga hacia arriba", a todas las llamadas previas)
    – abulafia
    Commented el 28 nov. 2019 a las 8:09
0

El código para realizarlo sin recursividad, que es la forma en la que estás presentando tu código sería así:

def is_sym(arr):
    return arr[::] == arr[::-1]

Pero, recursivamente tiene otra forma:

def is_sym(arr):
    if len(arr) < 2:
        return True
    elif arr[0] == arr[-1]:
        return is_sym(arr[1:-1])
    else:
        return False

Espero con esto entiendas mejor el código, analízalo bien para que los siguientes ejercicios los puedas hacer más fácilmente :D.

3
  • Muchas gracias. ¿Se podría implementar dicha llamada a la funcion en mi actualizacion de codigo, ya que me es un poco más visual ver el principio de "recursividad"?
    – Matilde
    Commented el 26 nov. 2019 a las 20:53
  • A tu código actualizado, se le modificaria esto: Linea 8 - if len(l1) != 1 and len(l1) != 2: Linea 10 - return is_sym2(l1[1:-1]) ; la Linea 9 en adelante debe de estar dentro del if de la linea 8. Con esto Tu código funcionaria, pero te recomiendo analizar el que te di, ya que es el MISMO pero sin lineas innecesarias. La llamada lo hacemos directamente en el return, ya que la funcion debe de retornar un boolean True o False. Commented el 26 nov. 2019 a las 23:11
  • Muchas gracias por la ayuda
    – Matilde
    Commented el 27 nov. 2019 a las 7:43

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.