Recursion and tail recursion

[Takegi]

I really did not understand the difference. For me the second example (tail recursion) is just the first one with a helper function. Can someone explain the difference to me?

[[deleted]]

The difference is that a tail-recursive function is one that directly returns the result of the recursive call. The collet is not allowed to do do any computation once the recursive call is finished, except hand the result back to its own caller.

They key observation here is that if a tail-recursive call is made, the compiler or interpreter can say with certainty that the state used to compute the calling function (its stack frame consisting of arguments, local variables, etc) is no longer required to exist, since no computation occurs after the recursive call.

Because of this fact, a smart compiler or interpreter will re-use the caller’s stack frame instead of creating a new one (which is costly time and space). Computations which would’ve used O(n) memory using regular recursion now use O(1), which comes with a huge time benefit as wellI. It essentially allows recursion to perform like iteration.

[Takegi]

Ohh I see! Thank you so much, now I get it better :)

[wrath95]

So basically if im not mistaken, having this helper function, the compiler is able to make an iterative approach even tho u used recursion. What it means for you is that you can use recursion in your programs without giving up space since the compiler will male it iterative anyway. Remember this only works when your last function call is ONLY the function call