0

En este caso particular, ¿cuál código es más eficiente? ¿el primero o el segundo?

// devuelve el ultimo elemento de la lista
int last( lista l ) {

    lista aux = l;

    while( aux->sig != NULL ) aux = aux->sig;
    return aux->elem;          
}

// devuelve el ultimo elemento de la lista
int last( lista l ) {

    lista aux = l;

    if( l->sig != NULL )
        return last( l->sig );
    else
        return( l->elem) ; 
}
6
  • 1
    Esto causa violación de segmento.
    – NaCl
    el 16 mar. 2018 a las 16:37
  • 2
    La versión iterativa es más eficiente porque cada llamada a una función implica la ejecución de las instrucciones de CPU necesarias para meter en la pila el parámetro y la dirección de retorno, junto con las instrucciones dentro de la función para acceder al parámetro en la pila y retornar. Además, las versiones recursivas hacen crecer la pila por cada llamada a la función, y ya que tienes una llamada por cada elemento de la lista, si la lista es larga puede producirse un stack overflow, peligro que no tienes en la versión iterativa.
    – abulafia
    el 16 mar. 2018 a las 16:49
  • OK. Entiendo que la recursividad sirve mas que nada para razonar mucho mejor un algoritmo dificil de hacerlo iteractivo, pero no tanto por la eficacia. Es así? el 16 mar. 2018 a las 17:26
  • La recursividad tal como lo dices sirve para razonar mucho mejor un algoritmo que puede ser difícil o mas largo hacerlo de manera iterativa, aunque siendo redundante, también complica las cosas, hace difícil de seguir el funcionamiento de un programa, cuantas veces se llamara a si misma?, que comportamiento tendrá?, cada vez que se llama debe agregar los parámetros a la pila, guardar la dirección de donde quedo el flujo antes de entrar a la función, asignar memoria a todas las variables locales etc... si llama a la funcion 100 veces, hace eso 100 veces.
    – Mario
    el 16 mar. 2018 a las 17:45
  • 2
    @Edu Efectivamente, la recursividad es una forma de razonar más matemática (como cuando se define un término de una serie en función del anterior, o como en una demostración matemática por inducción). Pero desde el punto de vista de la ejecución siempre es más eficiente una implementación iterativa. Hasta tal punto que muchos lenguajes funcionales contienen optimizaciones para convertir código recursivo en iterativo, permitiendo al programador expresarse de una forma más cercana a las matemáticas, pero ejecutándolo de una forma más eficiente para la arquitectura
    – abulafia
    el 16 mar. 2018 a las 18:45

0

Tu Respuesta

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

Examina otras preguntas con la etiqueta o formula tu propia pregunta.