Tasks in which recursion is either the fastest or only way to produce a result
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) &lt;= 1
        return list       
    pivot = first element of list
    lessList = []
    equalList = []
    greaterList = []
    for each element in list:
        if element &lt; pivot, add to lessList
        if element == pivot, add to equalList
        if element &gt; 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)