Problem on recursion

Question

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?

You are not calling function(20), function(19), ... as you are expecting, but function(20), function(20), function(20), .... Add print statements to check that if you want to be sure, or look at the definition of the post decrement operator. — coredump, Jan 15 '16 at 09:55
were you by chance [blocked at Stack Overflow](http://meta.programmers.stackexchange.com/q/7221/31260) for trying to use word 'problem' in question title? — gnat, Jan 15 '16 at 09:56
@KilianFoth thanx a lot......now i can proceed without crasing my app — aswal94, Jan 15 '16 at 09:59
@KilianFoth "Each function call will use some memory and if the data is big it will throw StackOverflowException.", I think you skimmed over this — aswal94, Jan 15 '16 at 10:17

score 3 · Accepted Answer · answered Jan 15 '16 at 10:17

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.

Only if the code is in a language where the last expression in a block is returned in lieu of a `return`-statement. Also, do you mean "guarantee" where you say "support" for C, because as far as I can see, that's ABI and QOI dependent. — Deduplicator, Jun 28 '18 at 12:50

Problem on recursion

1 Answers1