answersLogoWhite

0

What is difference between recursion and tail recursion?

Updated: 11/1/2023
User Avatar

Manju Kashyap

Lvl 1
4y ago

Best Answer

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.

User Avatar

Cristian Rutherford

Lvl 10
2y ago
This answer is:
User Avatar
User Avatar

Tomilola Babatunde

Lvl 1
7mo ago
so fun but not that fun
More answers
User Avatar

Ebrahim Muhammad Alw...

Lvl 2
8mo ago

the more ths vjgfuydefhj ebr uhiufr iuyeiure edyud

This answer is:
User Avatar

User Avatar

Tomilola Babatunde

Lvl 2
7mo ago

why

This answer is:
User Avatar

Add your answer:

Earn +20 pts
Q: What is difference between recursion and tail recursion?
Write your answer...
Submit
Still have questions?
magnify glass
imp
Related questions

What is the difference between left recursion and right recursion in a grammar?

Recursion is what it's called when a function calls itself. When a function calls itself immediately before returning, it's called tail recursion. Tail recursion can be more efficiently written as iteration. In fact a good compiler will recognize tail recursion and compile it as iteration. There is no such thing as left or right recursion in C programming.


Bring out the difference between recursion and iteration?

Recursion is repeatedly calling the function....---- whereas Iteration is nothing but just looping until condition doesn't satisfy.....


What is the answer for what is the difference between an ape and a monkey?

a ape has no tail and a monkey has a tail


How many types of recursion are there in c language?

Recursion in c language is a method where the function calls itself, within or outside the scope. Using Recursion, complicated problems can be divided into smaller parts so that solving them becomes more manageable. The recursion technique is available in Java, JavaScript, and C++.serves the same purpose. The type of Recursion in C • Direct Recursion • Indirect Recursion. Direct Recursion Recursion can call the function n-number of times. In the case of direct Recursion, the function calls itself inside the same position or in the local scope Direct Recursion problems are the Fibonacci series, a program to print 50 natural numbers. Indirect Recursion In the case of Indirect Recursion, a function X calls function Y, and function Y calls any function Z. Under certain conditions, function Z calls function A. In this case, function A is indirectly related to function Z. Indirect Recursion is also known as mutual Recursion, as more than one function runs a program. It is a two-step recursive function call process for making a recursive function call. Below mentioned are also type of Recursion: Tail Recursion No Tail/Head Recursion Linear Recursion Tree Recursion Tail Recursion A function is said to be tail recursion if it calls itself and also calls the last or the previous statement executed in the process. Head Recursion A function is said to be Head Recursion if it calls itself and also calls the first or the beginning statement executed in the process. Linear Recursion A function is said to be a linear recursive function if it makes a single call to itself each time the procedure executes itself and grows linearly depending on the size of the problem. Tree Recursion Tree Recursion is different from linear Recursion. Rather than making only one call to itself, that function makes more than one recursive call to the process within the recursive function. Following are the steps to solve the recursive problem in C: Step 1: Create a function and assign the work a part should do. Step 2: Select the subproblem and assume that the function already works on the problem. Step 3: Get the answer to the subproblem and use it to resolve the main issue. Step 4: The 90% of the problem defined is solved.


What is the difference between one-tailed and two-tailed test?

no tail


The gross head in turbine installation is difference of level between?

it is difference between the water level from head race and tail race


What is the difference between plain guppies and fancy tail guppies?

The only difference is the tail is about 1 cm bigger Males usually aready have fancy tails i find


What is the difference between a straight tailed pig and a curly trailed pig?

one has a curly tail and the other has a straight tail


What do you mean by base case recursive case binding time runtime stack and tail recursion?

These terms are found in Recursion.1.Base Case:it is the case in recursion where the answer is known,or we can say the termination condition for a recursion to unwind back.For example to find Factorial of num using recursion: int Fact(int num){ if(num==1 num==0)//base casereturn 1;else // recursive case: return num*Fact(num-1);} 2.Recursive case:It is the case whcih brings us to the closer answer. Run Time Stack:It is a system stack us to save the frame stack of a function every recursion or every call.This frame stack consists of the return address,local variables and return value if any. Tail Recursion:The case where the function consist of single recursive call and it is the last statement to be executed.A tail Recursion can be replace by iteration. The above function consists of tail recursion case.where as the below function does not. void binary(int start,int end,int el){int mid;if(end>start){mid=(start+end)/2;if(el==ar[mid])return mid;else{if(el>ar[mid])binary(mid+1,end,ele);elsebinary(start,mid-11,ele);


What is the difference between variating tail lights on a Datsun Nissan 280zx?

well


What is the difference between mock tail and a cocktail?

A mocktail (or virgin cocktail) is nonalcoholic.


Is there any difference between a dragonfly pendant with a curved tail over a straight tail?

no their the same thing but one has a curve and the other doesn't.