What are the advantages of the recursion in c plus plus?

Answer 1

Any problem that can be solved by dividing the problem into smaller problems of the same type is a good candidate for recursion. However, there are actually very few applications that cannot be resolved more efficiently with an iterative loop. It therefore pays to know when recursion is unavoidable and when it is optional.

The main benefit to recursion is that each instance of the function maintains its own set of non-static local variables completely independently of all other instances. But if these variables are of no use to the function when a recursive call returns, then an iterative implementation would be more efficient. Function calls are expensive in terms of memory consumption and performance, so the fewer we make, the better.

A classic example of recursive application is the quicksort algorithm. In simple terms, quicksort is a function that accepts a subset of data. The data is usually stored in an array and the function accepts the left and right index of the subset to be sorted. Initially this will be lower and upper bounds of the entire array, but if the indices indicate a subset with fewer than 2 items, the function immediately exits. This effectively defines the return path from the recursions.

Assuming there are 2 or more items, the function selects one of the items (the pivot) and then sorts the array such that items less than the pivot are placed to its left, and items greater or equal to its right. This moves the pivot into its final position, but the items on either side may still be unsorted. Thus the function calls itself twice, once for each of these subsets, which gradually reduces the problem down into smaller and smaller subsets until a subset has fewer than 2 items, at which point the recursion unwinds to the previous instance.

Recursion is required because when the first recursive call returns, the subset to the left of the pivot is guaranteed to be sorted, but the subset to the right is not. This means we must maintain local variables in order to determine the lower and upper bounds of that subset.

Although quicksort is an elegant application of recursion, there is still room for improvement. Firstly, it is better to make a recursive call upon the smaller of the two subsets. The smaller the subset, the fewer recursions that will be incurred sorting it.

Secondly, since the second recursion is also the last statement in the function, there is no need to maintain the local variables when it returns. Thus the second recursion can be implemented as a tail call. This effectively means we modify the existing local variables to suit and then recall the same instance (with a goto). This reduces the depth of recursion by one function call per recursion which will quickly add up to a significant boost in efficiency.

Answer 2

The same as in any other language. Any function that calls itself is a recursive function. An iterative function is one that contains a loop. If an iterative function calls itself (whether inside the loop or not), then the function is both recursive and iterative.

Answer 3

Recursion is a looping technique, whereby a function recursively calls itself. Although recursive code is often an elegant solution to a problem, an iterative solution is often more efficient, even if the code isn't quite as clean. However, sometimes recursion is the only option.

A typical example of recursion is used in the quick sort algorithm. The algorithm takes an array with an upper and lower index, selects a pivot, then sorts the array into two partitions, placing the pivot in between. The left partition contains values lower than the pivot while the right partition contains values greater than or equal to the pivot. The pivot is sorted, but the two partitions may not be. So the algorithm calls itself to repeat the process with each of these two partitions, which will gradually divide and conquer the partitions with each recursion. When a partition has fewer than 2 items, it is sorted, and the recursion can "unwind" one level. Since it is a finite process, sooner or later all the recursions will unwind to the original instance, at which point the entire array is sorted.

While the algorithm is quite elegant and highly efficient, it can be made even more efficient by making one recursive call upon the smaller partition, and make a tail-call on the larger partition. A tail-call is an iterative process which can be employed whenever the final instruction in a function is a recursive call. Rather than waste time calling a function that is all but complete apart from the recursive call, we can simply alter the parameters in the current instance and iterate it one more time. The overhead in altering the parameters more than offsets the expense of making a function call and ultimately reduces the depth of the recursion (because smaller partitions require fewer recursions).

Although it is possible to eliminate both recursions and make the process totally iterative, the additional overhead of doing so would actually be much worse than making a recursive call. The advantage of the recursion is that the state of each instance is preserved, and we require that state to be preserved in order to make the iterative call whenever a recursion unwinds.

That's the real trick with recursion: recognising when it is necessary and when it is not. It's really just a case of determining which method is the most efficient.

Other examples of recursion occur when dealing with fractals and factorials; anything that can be divided and conquered. Any function that alters its own parameters such that those parameters can be fed into the same function are good candidates for recursion. However, it's important to maintain efficiency. Most recursions can be implemented with iterative loops so it's often worth trying both techniques to see which works best in each situation. Ultimately, remember that every function call, even a recursive call, is an expensive overhead.

Answer 4

Recursion is a replacement of loop in programming.Recursive programming techniques are not recommended as it may lead to non terminating conditions and finally program crash.Recursion is only recommended if the program demands it.

Mainly Recursion is used for Operations like calculating factorial of a program.

Answer 5

The only advantage to recursion is that each call maintains the local variables of the previous call, which can be recalled as each recursion returns. If you have no need for these variables upon return, then recursion will be detrimental to performance. An iterative loop would offer better performance in these cases.

Answer 6

A recursive function is one that calls itself. A very simple, often cited, example is N Factorial...

int nfactorial (int n) if (n < 2) return 1 else if (n < 3) return n else return n * nfactorial (n - 1);

... which works by stacking up various values of n and then multiplying them all together when the unstacking occurs.

Unfortunately, this example suffers from failure at even small values of n due to integer overflow, but it serves to illustrate recursive calling. (nmax32 = 12, nmax64 = 20)

Answer 7

C language is promining languge in which in a clude in a thing