What is the difference between recursion and tail recursion?

Answer 1

The original answer really doesn't explain much, and almost nothing that's relevant to the question. (Sorry!) The part about iterations typically involving some kind of loop is on target, though it doesn't really shed much light.

This might best be explained by giving two pseudo-code examples, a function to calculate the factorial of an input argument. For simplicity's sake, since this is just to show examples, we will assume that we can be sure that the argument is a positive integer.

# This is an iterative function to calculate the factorial

Function I-Factorial(x)

Result = 1

For i = 1 to x

Result = Result * i

Next i

Return Result

End Function

# This is a recursive function to calculate the factorial

Function R-Factorial(x)

If x = 1 then

Return 1

Else

Return x * R-Factorial(x-1)

End If

End Function

Instead of stepping through a loop, the recursive function simply invokes itself, each invocation using an argument that's been reduced by 1 until ultimately it receives an argument of "1". Then the call for "R-Factorial(1)" is returned to the call for "R-Factorial(2)", which passes its result up to the call for "R-Factorial(3)", which passes its result up to the call for "R-Factorial(4)", and so on, until the accumulated result has bubbled its way up to the original call for "R-Factorial(x)".

As noted in the original answer, recursive functions can(but do not have to) incur additional overhead in terms of call stacks, memory allocations, and so on. If you write in assembly language (as I used to) and utilize reentrant coding techniques, the overhead is very close to zero.

=========

1. Recursion:

# When a recursive call is made, the method/process copies or clones itself, making new copy of:

* the code

* the local variables (with their initial values),

* the parameters

2. Iteration : there is no recursive call involved that saves a lot of time and space too as no extra space is needed to store each copy generated in recursion.

Iterative codes usually refers to codes that contain explicit iteration processes, that is, loops.

Answer 2

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 3

They are different things

recursion: when a part of code calls itself (directly or indirectly)

iteration: work in cycle