CODEWITHSUNDEEP
javajavascriptc#recursiontail-recursion
Bennett Yeo
Bennett Yeo

Reputation: 829

Detection of tail recursion in programming langs

The question has partial answers here and here which seem to implicitly imply that javascript and python result in 'infinite recursion'.

Background

Lately I've been dabbling in tail recursion which to my current understanding is that the programming style (*generally) holds the benefit of performance of an equivalent iterative solution with the benefit of readability -essentially making it the best of both worlds.

Examples

I've noticed that if one were to do this in .NET or Java:

while(true) {...}

Eventually Windows brings up a dialog box that allows the machine user to alter such said executable's state:

The famous windows not responding dialog box

The question

Since tail recursion (*practically) doesn't have to deal with the stackoverflow exception here, am I incorrect to assume that Java or C# would either:

  1. Trigger the "Foo.exe not responding" dialog
  2. Result in infinite recursion

Additionally, I am correct in assuming that this runtime 'exception' would be handled by the language's interpreter?

Upvotes: 1

Views: 142

Answers (1)

Stephen C
Stephen C

Reputation: 718826

Since tail recursion (*practically) doesn't have to deal with the stackoverflow exception here, am I incorrect to assume that Java or C# would either ...

This contains an incorrect assumption.

Tail recursion is simply a pattern in the source code.

It is tail recursion optimization that turns the recursive code into code that is iterative ... behind the scenes. The optimization needs to be performed by a compiler1.

The Java compilers (bytecode and JIT) in current generation Hotspot implementations do not do tail recursion optimization. There are security-related reasons for this.

But ignoring that:

Am I incorrect to assume that Java or C# would either:

  1. Trigger the "Foo.exe not responding" dialog
  2. Result in infinite recursion

There is a third case. It could go into an infinite loop without triggering the "not responding" alert. My understanding is that that alert only gets displayed when the OS detects that the application has not "consumed" or "responded to" a pending GUI event within a certain number of seconds.

I would expect the third case in the following scenarios:

  • The test application has no GUI
  • The test application doesn't run the the recursion test on the event thread
  • The user doesn't attempt to interact with the test application GUI in any way

Additionally, I am correct in assuming that this runtime 'exception' would be handled by the language's interpreter?

If there is a "stack overflow" event in Java, then the JVM runtime will turn it into a StackOverflowError exception. Whether it is the interpreter or "something else" that does this depends on ... whether the code was being interpreted at the time.

The resulting exception is thrown for the application itself to "handle" ... or ignore.

1 - To be pedantic, you could perform the optimization by hand at the source code level, but then your source code isn't recursive ...

Upvotes: 3

Related Questions