[Solved]: Tasks in which recursion is either the fastest or only way to produce a result

Problem Detail: 

I've just finished studying recursion at university. One thing that stood out for me however was that in both the lectures and in the practical we completed, all the tasks we were asked to do could be performed faster, and in less code, using iterative means.
This was something the lecturer confirmed.

Could somebody please give me some examples of situations when recursion is a better solution than iterative techniques? Additionally, are there any situations in which recursion is the only way to sole a problem?

Asked By : Andrew Martin

Answered By : jmite

There are no questions which can only be solved with recursion. This is because they can be solved with Turing machines, which don't use recursion.

The set of problems which can be solved with a TM are exactly the same as the ones which can be solved with recursion (or its formal model, the Lambda Calculus).

In particular, if you want to simulate recursion iteratively, the way to do this is to use a data structure called a stack (which simulates the call stack for functions).

As for algorithms that can be solved better using recursion, there are tons. I'm surprised that your recursive versions were longer, as recursion usually leads to less code. This is one of the reasons haskell is gaining popularity.

Consider the algorithm quicksort, for sorting lists. In rough pseudocode, it's as follows:

function quicksort(list)     if length(list) <= 1         return list            pivot = first element of list     lessList = []     equalList = []     greaterList = []     for each element in list:         if element < pivot, add to lessList         if element == pivot, add to equalList         if element > pivot, add to greater list    sortedLess = quicksort(lessList)    sortedGreater = quicksort(greaterList)    return sortedLess ++ equalList ++ sortedGreater 

where ++ means concatenation.

The code isn't purely functional, but by dividing the list into different parts, and sorting each sublist recursively, we get a very short $O(n\log n)$ sort.

Recursion is also very useful for recursive data structures. Often times you'll have a traversal on trees, of the following form:

function traverseTree(tree)     if (tree is a single node)         do something to that node     else, for each child of tree:          traverseTree(child) 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9987