c++ recursion exits without obvious reason

Question

I wrote a function using a recursion. While testing it, it turned out, that the function is killed without any obvious reason, while the recursion is still running.

To test this, I wrote an infinite recursion.

On my PC this function quits after about 2 seconds and the last output is about 327400. The last number isn't always the same.

I am using Ubuntu Lucid Lynx, the GCC compiler and Eclipse as IDE. If somebody has an idea what the problem is and how I can prevent the program from exiting I would be really pleased.

#include <iostream>

void rek(double x){
    std::cout << x << std::endl;
    rek(x + 1);
}

int main(int argc, char **argv) {
    rek(1);
}

Answer 1

You are most likely overflowing the stack, at which point your program will be summarily killed. The depth of the stack will always limit the amount you can recurse, and if you are hitting that limit, it means your algorithm needs to change.

Answer 2

I think you are right in expecting the code to run forever, as explained in

How do I check if gcc is performing tail-recursion optimization?

your code should be able to run for ever and ever, if gcc is performing tail recursion. On my machine it looks like -O3 actually makes gcc generate tail calls and actually flatten the stack. :-)

I surgest you set the optimize flag to O2 or O3.

Answer 3

You are causing a stack overflow (running out of stack space) because you don't provide an exit condition.

void rek(double x){
   if(x > 10)
      return;
   std::cout << x << std::endl;
   rek(x + 1);
}

Answer 4

Are you expecting this to work forever?

It won't. At some point you're going to run out of stack.

Answer 5

This is funny, talking about stack overflow on stackoverflow.com. ;) The call stack is limited (you can customized it from the project settings), but at some point, when you have infinite loop calls, it will be exceed and your program terminated.

Answer 6

If you want to avoid a stack overflow with infinite recursion, you're unfortunately going to have to delve into some assembly in order to change the stack so that a new activation record isn't constantly pushed onto the stack, which after some point will cause the overflow. Because you make the recursive call at the end of the function, this is called in other languages where recursion is popular (i.e., Lisp, Scheme, Haskell, etc.) a trail-call optimization. It prevents a stack overflow by basically transforming the tail-call into a loop. It would be something like this in C (note: I'm using inline assembly with gcc on x86, and I changed your arguments to int from double in order to simplify the assembly. Also I've changed to C from C++ in order to avoid name-mangling of function-names. Finally the "\n\t" at the end of each statement is not an actual assembly command but is needed for inline assembly in gcc):

#include <stdio.h>

void rek(int x)
{
    printf("Value for x: %d\n", x);

    //we now duplicate the equvalent of `rek(x+1);` with tail-call optimization

    __asm("movl 8(%ebp), %eax\n\t"   //get the value of x off the stack
          "incl %eax\n\t"            //add 1 to the value of x
          "movl 4(%ebp), %ecx\n\t"   //save the return address on the stack
          "movl (%ebp), %edx\n\t"    //save the caller's activation record base pointer
          "addl $12, %ebp\n\t"       //erase the activation record
          "movl %ebp, %esp\n\t"      //reset the stack pointer
          "pushl %eax\n\t"           //push the new value of x on the stack for function call
          "pushl %ecx\n\t"           //push the return value back to the caller (i.e., main()) on the stack
          "movl %edx, %ebp\n\t"      //restore the old value of the caller's stack base pointer
          "jmp rek\n\t");            //jump to the start of rek()
}

int main()
{
    rek(1);
    printf("Finished call\n");  //<== we never get here

    return 0;
}

Compiled with gcc 4.4.3 on Ubuntu 10.04, this ran pretty much "forever" in an infinite loop with no stack overflow, where-as without the tail-call optimization, it crashed with a segmentation fault pretty quickly. You can see from the comments in the __asm section how the stack activation record space is being "recycled" so that each new call does not use up space on the stack. This involves saving the key values in the old activation record (the previous caller's activation record base pointer and the return address), and restoring them, but with the arguments changed for the next recursive call to the function.

And again, other languages, mainly functional languages, perform tail-call optimization as a base-feature of the language. So a tail-call recursive function in Scheme/Lisp/etc. won't overflow the stack since this type of stack manipulation is done under-the-hood for you when a new function call is made as the last statement of an existing function.

Answer 7

Well you have defined infinite recursion and overflowing the stack, which kills your app. If you really want to print all numbers; then use a loop.

int main(...)
{
   double x = 1;
   while (true)
   {
       std:cout << x << std::endl;
       x += 1;
   }
 }

Answer 8

Each recursive method should implement an exit condition, otherwise you will get stack overflow and the program will terminate.

In your case, there is no condition on the parameter you are passing to the function,hence, it runs forever and eventually crashes.