14
$\begingroup$

In a Part Test for GATE Preparation there was a question :

f(n):
     if n is even: f(n) = n/2
     else f(n) = f(f(n-1))

I answered "It will terminate for all integers", because even for some negative integers, it will terminate as Stack Overflow Error.

But my friend disagreed saying that since this is not implemented code and just pseudocode, it will be infinite recursion in case of some negative integers.

Which answer is correct and why?

$\endgroup$
  • 8
    $\begingroup$ It doesn't terminated for n=-1. Mostly theoretical limits are considered in such cases. $\endgroup$ – Deep Joshi Jun 15 '18 at 6:58
  • 9
    $\begingroup$ If stack overflow is to be considered as termination, then all programs will terminate and it defeats the purpose of this question... $\endgroup$ – xuq01 Jun 15 '18 at 10:53
  • 10
    $\begingroup$ @xuq01 while (true); won't terminate nor, on anything sensible, cause stack overflow. $\endgroup$ – TripeHound Jun 15 '18 at 12:39
  • 3
    $\begingroup$ @leftaroundabout I probably shouldn't have used "on anything sensible" because it's a completely different level of "sensible"... spotting and implementing tail recursion is nice (or even sensible), but not doing so is only slightly "not sensible". Anything that implemented while(true); in a way that uses any stack would most definitely be not sensible. The point is, unless you deliberately went out of your way to be awkward, while(true); will neither terminate nor trigger stack overflow. $\endgroup$ – TripeHound Jun 15 '18 at 13:20
  • 14
    $\begingroup$ @xuq01 I don't think the "destruction of the universe" counts as a solution to the halting problem. $\endgroup$ – TripeHound Jun 15 '18 at 16:54
49
$\begingroup$

The correct answer is that this function does not terminate for all integers (specifically, it does not terminate on -1). Your friend is correct in stating that this is pseudocode and pseudocode does not terminate on a stack overflow. Pseudocode is not formally defined, but the idea is that it does what is says on the tin. If the code doesn't say "terminate with a stack overflow error" then there is no stack overflow error.

Even if this was a real programming language, the correct answer would still be "does not terminate", unless the use of a stack is part of the definition of the language. Most languages do not specify the behavior of programs that might overflow the stack, because it's difficult to know precisely how much stack a program will use.

If running the code on an actual interpreter or compiler causes a stack overflow, in many languages, that's a discrepancy between the formal semantics of the language and the implementation. It is generally understood that implementations of a language will only do what can be done on a concrete computer with finite memory. If the program dies with a stack overflow, you're supposed to buy a bigger computer, recompile the system if necessary to support all that memory, and try again. If the program is non-terminating then you may have to keep doing this forever.

Even the fact that a program will or will not overflow the stack is not well-defined, since some optimizations such as tail call optimization and memoization can allow an infinite chain of function calls in constant-bound stack space. Some language specifications even mandate that implementations perform tail call optimization when possible (this is common in functional programming languages). For this function, f(-1) expands to f(f(-2)); the outer call to f is a tail call so it doesn't push anything on the stack, thus only f(-2) goes onto the stack, and that returns -1, so the stack is back to the same state it was in at the beginning. Thus with tail call optimization f(-1) loops forever in constant memory.

$\endgroup$
  • 3
    $\begingroup$ An example where the code translated to a programming language results in no stack overflow is Haskell. It just loops indefinitely: let f :: Int -> Int; f n = if even n then n `div` 2 else f (f (n - 1)) in f (-1) $\endgroup$ – JoL Jun 15 '18 at 15:36
5
$\begingroup$

If we look at this in terms of the C language, an implementation is free to replace code with code that produces the same result in all cases where the original doesn't invoke undefined behaviour. So it can replace

f(n):
   if n is even: f(n) = n/2
   else f(n) = f(f(n-1))

with

f(n):
   if n is even: f(n) = n/2
   else f(n) = f((n-1) / 2)

Now the implementation is allowed to apply tail recursion:

f(n):
   while n is not even do n = (n-1) / 2
   f(n) = n/2

And this loops forever if and only if n = -1.

$\endgroup$
  • $\begingroup$ I think, in C, that invoking f(-1) is undefined behavior (the implementation may assume that every thread either terminates or does something else in a short list of activities that this function does not do), so the compiler can actually do anything it wants in that case! $\endgroup$ – user5386 Jun 17 '18 at 8:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.