CODEWITHSUNDEEP
cstack-overflowtermination
Beyond.Multiverse
Beyond.Multiverse

Reputation: 73

Abnormal Termination due to stack overflow

I recently wrote my Grad school Admission test few days back and the following question appeared in the test.
When the below function is invoked with any positive integer as argument, does it terminate? Also does it print anything?

void convert (int n) 
{
  if (n < 0)
    printf ("%d", n);
  else 
  {
    convert (n/2);
    printf ("%d", n%2);
  }
}

According to me, nothing will be printed as the control never reaches inside the if statement and also since the printf statement is placed after the function call under else block. The value of n never reaches below 0 and the function calls itself again and again till the stack overflows. My question is whether the code will abnormally terminate because of stack overflow?

Upvotes: 6

Views: 611

Answers (3)

thb
thb

Reputation: 14464

Yes, unless your compiler's optimizer does something unusual, this program will abnormally terminate because of stack overflow.

The reason is that the convert() function is recursively called infinitely many times. You knew that already, but the point is this: each recursive entry to convert() pushes a new frame onto the stack. Each frame includes a return address to the previous frame and a local value of n.

Compilers have optimizers but it would take an unusual optimizer to intuit that this function (a) has no side effects and (b) returns no value. It is unlikely therefore that the optimizer would save this code from abnormal termination.

I believe that you have answered this question right.

Meanwhile, a commenter has reminded us of a special case, tail recursion. If the recursive call had ended the function, as return convert(n/2); for example, then the compiler could have reused a single stack frame for all recursive invocations. Reason: by the time the recursive call occurs, the current invocation no longer requires its storage; the object n could safely be overwritten by the new n for the recursive call; only the return address to the original caller would need to be retained. If tail recursion applied, the stack would not grow and, therefore, the program would not terminate, neither abnormally nor otherwise. However, tail recursion does not apply here.

Upvotes: 4

Jabberwocky
Jabberwocky

Reputation: 50883

The code will terminate with a stackoverflow or not depending on the compiler output.

There will be no output. because n will never be smaller than 0.

With a naive compiler that does compile the recursion without optimisation, you will get a stackoverflow on most (if not all) implementations.

Upvotes: 3

Govind Parmar
Govind Parmar

Reputation: 21562

The code will not terminate with a positive integer argument since the base condition n < 0 will never be met.

The recursive call to convert calls it with the argument n / 2, which, as integer division, will inevitably reach zero, but never less than it.

For example, with the argument 10:

call convert(10)
10 < 0 is false; enter the else branch
call convert(10 / 2)
5 < 0 is false; enter the else branch
call convert(5 / 2)
2 < 0 is false; enter the else branch
call convert(2 / 2)
1 < 0 is false; enter the else branch
call convert(1 / 2)
0 < 0 is false; enter the else branch
call convert(0 / 2)
0 < 0 is false; enter the else branch
call convert(0 / 2)
0 < 0 is false; enter the else branch
call convert(0 / 2)
0 < 0 is false; enter the else branch

It will never enter the base case.

Upvotes: 6

Related Questions