What is difference between recursion and tail recursion?

Answer 1

Tail recursion is a compiler optimisation. When the final statement of a function is a recursive call into the same function, the compiler can eliminate that call completely. Consider the (simplified) quicksort algorithm:

void qsort (int* array, unsigned lbound, unsigned ubound) {

unsigned pivot;

if (lbound>=ubound) return;

pivot = partition (array, lbound, ubound);

qsort (array, lbound, pivot-1);

qsort (array, pivot+1, ubound);

}

This function has two recursive calls, however the second call is a tail recursion because as soon as we return from that instance of the function, we also return from the current instance. As a result, the values of the local variables are no longer relevant to the current instance. That being the case, instead of calling the function a second time and thus creating new instances of all the local variables, we can simply change the values of the current local variables and re-invoke the same instance a second time. In essence, the compiler will re-write the above function so that it is functionally equivalent to the following:

void qsort (int* array, unsigned lbound, unsigned ubound) {

unsigned pivot;

tail_call:

if (lbound>=ubound) return;

pivot = partition (array, lbound, ubound);

qsort (array, lbound, pivot-1);

lbound=pivot+1;

goto tail_call;

}

Note that (in this example) we only need to change the value of one local variable, lbound, and then jump to the tail_call label.

With modern compilers, tail recursion is done automatically for us. This means we can write recursive functions in the normal manner and thus keep the function in a readable (and thus maintainable), and let the compiler deal with the complexities of implementing the tail recursion.

We could, of course, implement tail recursion manually if we wish, but there is no advantage in doing so, it just makes code that little bit more difficult to read and thus more difficult to maintain. The compiler is there to help you write cleaner code so it makes sense to enlist its help whenever possible.

Answer 2

the more ths vjgfuydefhj ebr uhiufr iuyeiure edyud

Answer 3

why