I know the general concept of recursion. I came across the concept of tail recursion while studying the quicksort algorithm. In this video of quick sort algorithm from MIT at 18:30 seconds the professor says that this is a tail recursive algorithm. It is not clear to me what tail recursion really means.
Can someone explain the concept with a proper example?
Some answers provided by the SO community here.
Asked By : Geek
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6230
Answered By : Matt Lewis
Tail recursion is a special case of recursion where the calling function does no more computation after making a recursive call. For example, the function
int f(int x, int y) { if (y == 0) { return x; } return f(x*y, y-1); } is tail recursive (since the final instruction is a recursive call) whereas this function is not tail recursive:
int g(int x) { if (x == 1) { return 1; } int y = g(x-1); return x*y; } since it does some computation after the recursive call has returned.
Tail recursion is important because it can be implemented more efficiently than general recursion. When we make a normal recursive call, we have to push the return address onto the call stack then jump to the called function. This means that we need a call stack whose size is linear in the depth of the recursive calls. When we have tail recursion we know that as soon as we return from the recursive call we're going to immediately return as well, so we can skip the entire chain of recursive functions returning and return straight to the original caller. That means we don't need a call stack at all for all of the recursive calls, and can implement the final call as a simple jump, which saves us space.
Post a Comment