What is the importance of recursion?

Answer 1

In computer science, complex problems are resolved using an algorithm. An algorithm is a sequence of specific but simple steps that need to be carried out in a procedural manner. Some steps may need to be repeated in which case we will use an iterative loop to repeat those steps. However, sometimes we encounter an individual step that is actually a smaller instance of the same algorithm. Such algorithms are said to be recursive.

An example of a recursive algorithm is the factorial algorithm. The factorial of a value, n, is the product of all values in the range 1 to n where n>0. If n is zero, the factorial is 1, otherwise factorial(n)=n*factorial(n-1). Thus the factorial of any positive value can be expressed in pseudocode as follows:

function factorial (num)

{

if num=0 then return 1

otherwise;

return num * factorial (num-1);

}

Note that any function that calls itself is a recursive function. Whenever we use recursion, it is important that the function has an exit condition otherwise the function would call itself repeatedly, creating an infinite recursion with no end. In this case the exit condition occurs when n is 0 which returns 1 to the previous instance. At this point the recursions begin to "unwind", such that each instance returns its product to the previous instance. Thus if num were 3, we get the following computational steps:

factorial(3) = 3 * factorial(3-1)

factorial(2) = 2 * factorial(2-1)

factorial(1) = 1 * factorial(1-1)

factorial(0) = 1

factorial(1) = 1 * 1 = 1

factorial(2) = 2 * 1 = 2

factorial(3) = 3 * 2 = 6

Note how we cannot calculate 3 * factorial(3-1) until we know what the value of factorial(3-1) actually is. It is the result of factorial(2) but, by the same token, we cannot work out 2 * factorial(2-1) until we know what factorial(2-1) is. We continue these recursions until we reach factorial(0) at which point we can begin working our way back through the recursions and thus complete each calculation in reverse order. Thus factorial(3) becomes 1*1*2*3=6.

Although algorithms that are naturally recursive imply a recursive solution, this isn't always the case in programming. The problem with recursion is that calling any function is an expensive operation -- even when it is the same function. This is because the current function must push the return address and the arguments to the function being called before it can pass control to the function. The function can then pop its arguments off the stack and process them. When the function returns, the return address is popped off the stack and control returned to that address. All of this is done automatically, Behind the Scenes, in high-level languages. Compilers can optimise away unnecessary function calls through inline expansion (replacing the function call with the actual code in the function, replacing the formal arguments with the actual arguments from the function call). However, this results in increased code size, thus the compiler has to weigh up the performance benefits of inline expansion against the decreased performance from the increased code size. With recursive functions, the benefits of inline expansion are quickly outweighed by the code expansion because each recursion must be expanded. Even if inline expansion is deemed beneficial, the compiler will often limit those expansions to a predetermined depth and use a recursive call for all remaining recursions.

Fortunately, many recursive algorithms can be implemented as an iterative loop rather than a recursive loop. This inevitably leads to a more complex algorithm, but is often more efficient than inline expansion. The factorial example shown above is a typical example. First, let's review the recursive algorithm:

function factorial (num)

{

if num=0 then return 1

otherwise;

return num * factorial (num-1);

}

This can be expressed iteratively as follows:

function factorial (num)

{

let var := 1

while 1 < num

{

var := var * num

num := num - 1

}

end while

return var;

}

In this version, we begin by initialising a variable, var, with the value 1. We then initiate an iterative loop if 1 is less than num. Inside the loop, we multiply var by num and assign the result back to var. We then decrement num. If 1 is still less than num then we perform another iteration of the loop. We continue iterating until num is 1 at which point we exit the loop. Finally, we return the value of var, which holds the factorial of the original value of num.

Note that when the original value of num is either 1 or 0 (where 1 would not be less than num), then the loop will not execute and we simply return the value of var.

Although the iterative solution is more complex than the recursive solution and the recursive solution expresses the algorithm more effectively than the iterative solution, the iterative solution is likely to be more efficient because all but one function call has been completely eliminated. Moreover, the implementation is not so complicated that it cannot be inline expanded, which would eliminate all function calls entirely. Only a performance test will tell you whether the iterative solution really is any better.

Not all recursive algorithms can be easily expressed iteratively. Divide-and-conquer algorithms are a case in point. Whereas a factorial is simply a gradual reduction of the same problem, divide-and-conquer uses two or more instances of the same problem. A typical example is the quicksort algorithm.

Quicksort is ideally suited to sorting an array. Given the lower and upper bounds of an array (a subarray), quicksort will sort that subarray. It achieves this by selecting a pivot value from the subarray and then splits the subarray into two subarrays, where values that are less than the pivot value are placed in one subarray and all other values are placed in the other subarray, with the pivot value in between the two. We then sort each of these two subarrays in turn, using exactly the same algorithm. The exit condition occurs when a subarray has fewer than 2 elements because any array (or subarray) with fewer than 2 elements can always be regarded as being a sorted array.

Since each instance of quicksort will result in two recursions (one for each half of the subarray), the total number of instances doubles with each recursion, hence it is a divide-and-conquer algorithm. However, it is a depth-first recursion, so only one of the two recursions is executing upon each recursion. Nevertheless, each instance of the function needs to keep track of the lower and upper bounds of the subarray it is processing, as well as the position of the pivot value. This is because when we return from the first recursion we need to recall those values in order to invoke the second recursion. With recursive function calls we automatically maintain those values through the call stack but with an iterative solution the function needs to maintain its own stack instead. Since we need to maintain a stack, the benefits of iteration are somewhat diminished; we might as well use the one we get for free with recursion. However, when we invoke the second recursion, we do not need to recall the values that we used to invoke that recursion because when that recursion returns the two halves of the subarray are sorted and there's nothing left to do but return to the previous instance. Knowing this we can eliminate the second recursion entirely because, once we return from the first recursion, we can simply change the lower bound of the subarray and jump back to the beginning of the function. This effectively reduces the total number of recursions by half.

When the final statement of a function is a recursive call to the same function it is known as a "tail call". Although we can manually optimise functions to eliminate tail calls, compilers that are aware of tail call recursion can perform the optimisation for us, automatically. However, since the point of tail call optimisation is to reduce the number of recursions, it pays to optimise the call upon those recursions that would normally result in the greatest depth of recursion. In the case of quicksort, the deepest recursions will always occur upon the subarray that has the most elements. Therefore, if we perform recursion upon the smaller subarray and tail call the larger subarray, we reduce the depth of recursion accordingly.

Although recursions are expensive, we shouldn't assume that iterative solutions are any less expensive. Whenever we have a choice about the implementation, it pays to do some performance tests. Quite often we will find that the benefits of iteration are not quite as significant as we might have thought while the increased complexity makes our code significantly harder to read and maintain. Wherever possible we should always try to express our ideas directly in code. However, if more complex code results in measurable improvements in performance and/or memory consumption, it makes sense to choose that route instead.

Answer 2

Recursion is extremely important in computer science. It provides a short and simple way to write a piece of code that can repeat itself as needed with a minimum number of variables. Sometimes recursion allows the program to run more quickly while other times a loop comes to the answer more quickly. Both have their place.

Answer 3

Recursion is dangerous yet powerful tool.

It is dangerous because it can lead to bad programs in terms of time and space when not used properly.

Recursion is needed in implementing very good graph related algorithms such as graph traversal.

Recursion shows it's real power for the problems which have underlying concept of stack.Stack can be best implemented using only with recursion.

Answer 4

The Reasons are :->

1> The length of the program code is shorter while using a recursive function rather than a normal function.

2> Using a recursive function, this function needs to be called only once from the main function and passing the initial parameters to it at the function call. So the number of times of function calls using a recursive function is approximately equal to 1, which is always greater in the case of normal function calls. Hence time is saved while execution.

3> The recursive code is of utmost importance and this determines the level of the programmer.

4> Recursion is generally preferred as being the choice of good programmers.