3

He creado la siguiente funcion:

void imprimir(void){
    cout << "Y\n";
    imprimir();
}

Intentando aprender mas sobre la utilidad que podria tener el uso de una funcion recursiva (funcion que se llama a si misma).

Al incluirla en mi codigo, este ha quedado asi:

#include <iostream>

using namespace std;

void imprimir(void){
    cout << "Y\n";
    imprimir();
}

int main(void){

   imprimir();

   return 0;
}

Tan simple como que la funcion se ejecute y se siga ejecutando, me he encontrado con el siguiente problema.

Despues de unos segundos, aparecio este mensaje de error:

Segmentation fault: 11

Porque ocurre esto? Si la recursividad es un concepto de programacion y C++ soporta la recursividad, porque ha ocurrido este error, si la funcion no usa punteros ni nada fuera de lo comun.

Tarda alrededor de 8 segundos en dejar de funcionar. Es necesario incluir algun tiempo de espera?

2
  • Me parece que no es estas definiendo en que momento se va a romper la recursividad y se queda en un bucle infinito por eso te manda ese error.
    – M. Gress
    Commented el 27 mar. 2017 a las 20:41
  • Si, pero, si se pueden crear bucles infinitos while(true) y estos se ejecutan sin limite, porque no se podria hacer un "bucle", o bien, una ejecucion ilimitada con recursividad. Commented el 27 mar. 2017 a las 20:44

2 respuestas 2

7

Una llamada a función implica varias cosas: hay que colocar argumentos en la pila, y colocar en la misma pila la dirección de retorno (la dirección desde la que llamamos a la función). Eso, como mínimo.

Si realizas llamadas recursivas al infinito, mas pronto o mas tarde, la pila será tan grande que interferirá con el resto del programa, o se pasará del límite de tamaño del memoria por proceso que el sistema operativo tenga establecido.

Un while( ), por su parte, no es una llamada a función; no se colocan argumentos en la pila sin fin; se limita a realizar un ciclo, un salto a cierta dirección fija, sin necesidad de tocar la pila para nada.

En algunos lenguajes (C++ entre ellos, pero depende del compilador) es posible, no obstante, realizar llamadas recursivas sin fin. Es lo que se conoce como Tail Call Optimization. Es un truco, mediante el cual no se introducen nuevos elementos en la pila, sino que se reutiliza el contexto actual.

Si tu compilador lo soporta, puedes hacer

void imprimir(void){
  static const char msg = "Y\n";

  cout << msg;
  return imprimir();
}

sin llegar nunca a recibir el mensaje (pero disparando el uso de CPU).

Observa los sutiles cambios. Usamos un mensaje declarado como static, para que no se use la pila, y colocamos un return delante de la llamada recursiva.

Nota

C++ es famoso por las múltiples llamadas a constructores y destructores ocultas detras de operaciones aparentemente inocuas. Una simple asignación puede requerir múltiples llamadas a constructor/destructor, y cada una con su correspondiente uso de la pila. A partir de C++11, esto disminuye bastante (casi se elimina, gracias a los constructores move y idem operadores de asignación).

3
  • Quiza entendiste un poco mal lo que indicaba yo en los comentarios, no estaba confundiendo la recursividad con los ciclos, me referia que si uno puede usar un bucle para infinitas ejecuciones, porque una funcion recursiva no puede ejecutarse infinitas veces Commented el 27 mar. 2017 a las 21:04
  • Agradezco tu respuesta, me ha dejado claro el porque de este error. Commented el 27 mar. 2017 a las 21:05
  • @IvanBotero Como siempre, un placer :-) La pila, el marco de pila (stack frame), Tail Call Optimization, convenciones de llamada (call convention), ... son temas interesante. Si te defiendes en inglés, hay mucha info disponible.
    – Trauma
    Commented el 27 mar. 2017 a las 21:08
2
void imprimir(void){
    cout << "Y\n";
    imprimir();
}

Vamos a analizar el comportamiento de la aplicación:

imprime "Y"
llama a imprimir()
imprime "Y"
llama a imprimir()
imprime "Y"
llama a imprimir()
imprime "Y"
...

Y así hasta el infinito. ¿El problema? Que cada llamada a imprimir() consume espacio en la pila del programa ya que el sistema necesita saber a dónde tiene que volver cuando abandone la función a la que se está llamando.

Es fácil entender que en un espacio finito (la pila tiene un tamaño determinado) no entra una cantidad infinita de información (la llamada recursiva se repetirá indefinidamente). Así pues en algún momento la pila del programa se llenará y el Sistema Operativo matará la aplicación para proteger la integridad de la memoria del resto de procesos.

La recursividad necesita siempre un tope que limite el máximo de iteraciones so pena de provocar un mal funcionamiento del programa.

Un ejemplo:

void imprimir(int valor)
{
  if( valor < 0 ) return; // Para abandonar la recursividad
  std::cout << valor << '\n';
  imprimir(valor-1);
}

int main()
{
  imprimir(10);
}

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.