void function(int x){
if(x<=0)
return;
function(x--);
}
This is a recursion function which is called with the value of x = 20.
The Recursive call will take place in this way
function(20)...function(19).......function(0)
Each function call will use some memory and if the data is big it will throw StackOverflowException.
So what I want to know is:
Is there any way by which we can call a function and remove it from the call stack so that its memory can be utilized (eg. after function(20) calls function(19) the memory for function(20) should be de-allocated), and the the end of the recursive call (here function(0) ) it should get returned from the first place from where it was called (i.e. function(20)).
Can this be done in Java and C?
5
What you have here is a Tail Call, and even more, it is Tail Recursion (Direct Tail Recursion) to be precise.
Many languages have Proper Tail Calls (e.g. Scheme, ECMAScript), and even more languages have Proper Tail Recursion (e.g. Scala, at least for Direct Tail Recursion). Unfortunately, neither C nor Java support Proper Tail Calls or even the much weaker Proper Tail Recursion, so, for large enough values of x, you will blow the stack, there is no way around it.
Obviously, you have a bug in your code that leads to infinite recursion, which means even if you have Proper Tail Recursion, your program will run for an infinite amount of time.
Proper Tail Calls have the semantics of a subroutine call but the time and space performance of a GOTO (because they are in fact operationally equivalent to a GOTO and often implemented that way). Proper Tail Recursion, then, is obviously operationally equivalent to a GOTO back to the beginning of the subroutine. Or, in other words, a loop.
So, if your language has loops, but no Direct Tail Recursion, you can always replace Direct Tail Recursion with a loop with the same space and time performance, but losing the safety and readability properties of a subroutine call.
1