Recursion question. *Stack Overflows*

[triumphost]

I'm trying to understand recursion and stack overflows.

First, why does this not cause a stack overflow? Is it because the function returns every time and that the stack isn't populated upon each call?

void Meh()
{
}

int main()
{
   while (true)
     Meh();
}

Two, What is the difference between the two below? They both seem the exact same to me except one uses a base function aka the forward declaration and the other calls itself.. Will both of them result in the same stack overflow? Will they BOTH overflow at all? Both never seem to return to me so the Bleh recursion should overflow exactly like Meh's?

void Meh()
{
    Meh();
}


//Versus..

void Bleh();  //Forward Declaration.

void BaseR()
{
   Bleh();   //Call the forward..
}

void Bleh()
{
   BaseR();  //Call the base..
}

[deceptikon]

First, why does this not cause a stack overflow?

I'd wager that the empty function call was optimized away. You might be able to turn off all optimization switches in your compiler and get it to overflow.

Two, What is the difference between the two below?

The first is direct recursion and the second is indirect recursion. Direct recursion is when a function calls itself, and indirect recursion is where a function is called recursively by a different function that it calls. They're still both recursion, and can still both overflow the stack if not capped by a base case.

[mike_2000_17]

First, why does this not cause a stack overflow?

If you call a function in an infinite loop, you will not get a stack overflow. The stack is, well, a stack. Things get pilled on and pulled off. You enter a function, it uses some space on the stack for its variables, and when you leave the function, that space is released. So, repeatedly calling a function only causes spaces to be allocated and deallocated repeatidly on the stack, there is no net growth during the iterations.

Will both of them result in the same stack overflow? Will they BOTH overflow at all?

Your recursion calls will not result in stack overflow because their stack frames have a size of 0. You don't have any local variables, parameters, or return values. There is no reason to take up any space on the stack for that function (unless there are debugger-related things). So, you allocate 0 space on the stack an infinite amount of time, what is infinity * 0? Answer: 0.

Both never seem to return to me so the Bleh recursion should overflow exactly like Meh's?

Yeah, there is no difference from a stack-overflow perspective between direct and indirect recursions. The only thing that matters is the size of the stack frames required at each recursion, and if those recursions cause a growth of the stack usage (it is possible to have a non-zero stack frame, and yet have no stack growth, this is called a tail-recursion).

Here is a nicer program to test stack-overflows:

#include <iostream>
#include <iomanip>

#ifdef WIN32

#include <windows.h>

static std::size_t get_stack_size() {
  MEMORY_BASIC_INFORMATION mbi;
  VirtualQuery(&mbi, &mbi, sizeof(mbi));
  VirtualQuery(mbi.AllocationBase, &mbi, sizeof(mbi));
  VirtualQuery((char*)mbi.BaseAddress + mbi.RegionSize, &mbi, sizeof(mbi));
  VirtualQuery((char*)mbi.BaseAddress + mbi.RegionSize, &mbi, sizeof(mbi));
  return mbi.RegionSize;
}; 

#else

#include <pthread.h>

static std::size_t get_stack_size() {
  std::size_t stacksize;
  pthread_attr_t attr;
  pthread_attr_init(&attr);
  pthread_attr_getstacksize (&attr, &stacksize);
  return stacksize;
};

#endif

void print_countdown(int i) {
  int new_i = i - 1;
  std::cout << "\rCountdown to stack-overflow: " << std::setw(7) << new_i; std::cout.flush();
#ifdef WIN32
  Sleep(0);
#else
  usleep(0);
#endif
  print_countdown(new_i);
};


int main() {

  print_countdown(get_stack_size() / (8 * sizeof(std::size_t)));

  return 0;
};