Segmentation Fault - Recursion

Question

Segmentation Fault - Recursion

Navigation

#1 by (6 votes)
#2 by (2 votes)

3

I created the following function:

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

Trying to learn more about the usefulness of using a recursive function (a function that calls itself).

By including it in my code, this has been left like this:

#include <iostream>

using namespace std;

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

int main(void){

   imprimir();

   return 0;
}

As simple as the function is executed and is still running, I have encountered the following problem.

After a few seconds, this error message appeared:

Segmentation fault: 11

Why does this happen? If recursion is a programming concept and C ++ supports recursion, because this error has occurred, if the function does not use pointers or anything out of the ordinary.

It takes about 8 seconds to stop working. Is it necessary to include some waiting time?

c++

asked by Ivan Botero 27.03.2017 в 22:37

source

2 answers

2

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

We are going to analyze the behavior of the application:

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

And so on to infinity. The problem? That every call to imprimir() consumes space in the program's stack since the system needs to know where it has to return when it leaves the function to which it is being called.

It is easy to understand that in a finite space (the stack has a certain size) an infinite amount of information does not enter (the recursive call will be repeated indefinitely). So at some point the program's stack will be full and the Operating System will kill the application to protect the integrity of the memory of the rest of the processes.

Recursion needs always a cap that limits the maximum of iterations under penalty of causing a malfunction of the program.

An example:

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

int main()
{
  imprimir(10);
}

answered by 27.03.2017 в 23:00

'getMonth ()' is deprecated Have a text appear centered, with space above and below

score 6 · Accepted Answer

A function call implies several things: you have to put arguments in the stack, and place the return address in the same stack (the address from which you call the function). That, at least.

If you make recursive calls to infinity , sooner or later, the stack will be so large that it will interfere with the rest of the program, or the memory size limit will be exceeded by process that the operating system has been established.

A while( ) , meanwhile, is not a function call ; no arguments are placed in the endless stack; It is limited to a cycle, a jump to a certain fixed direction, without the need to touch the battery at all.

In some languages (C ++ between them, but depends on the compiler) it is possible, however, to make endless recursive calls . This is what is known as Tail Call Optimization . It is a trick , where no new elements are introduced in the stack , but the context is reused current.

If your compiler supports it, you can do

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

  cout << msg;
  return imprimir();
}

without ever receiving the message (but firing CPU usage).

See the subtle changes. We use a message declared as static , so that the stack is not used, and we place a return in front of the recursive call.

Note

C ++ is famous for the multiple calls to builders and destructors hidden behind of seemingly innocuous operations. A simple assignment may require multiple calls to constructor / destructor, and each one with its corresponding use of the stack. As of C ++ 11, this decreases considerably (it is almost eliminated, thanks to the constructors move and idem assignment operators).