Is recursion in scala very necessary?

Question

In the coursera scala tutorial, most examples are using top-down iterations. Partially, as I can see, iterations are used to avoid for/while loops. I'm from C++ and feel a little confused about this.

Is iteration chosen over for/while loops? Is it practical in production? Any risk of stackoverflow? How about efficiency? How about bottom up Dynamic Programming (especially when they are not tail-recusions)?

Also, should I use less "if" conditions, instead use more "case" and subclasses?

Answer 1

Truly high-quality Scala will use very little iteration and only slightly more recursion. What would be done with looping in lower-level imperative languages is usually best done with higher-order combinators, map and flatmap most especially, but also filter, zip, fold, foreach, reduce, collect, partition, scan, groupBy, and a good few others. Iteration is best done only in performance critical sections, and recursion done only in a some deep edge cases where the higher-order combinators don't quite fit (which usually aren't tail recursive, fwiw). In three years of coding Scala in production systems, I used iteration once, recursion twice, and map about five times per day.

Answer 2

Hmm, several questions in one.

Necessity of Recursion

1. Recursion is not necessary, but it can sometimes provide a very elegant solution.
2. If the solution is tail recursive and the compiler supports tail call optimisation, then the solution can even be efficient.
3. As has been well said already, Scala has many combinator functions which can be used to perform the same tasks more expressively and efficiently.

One classic example is writing a function to return the nth Fibonacci number. Here's a naive recursive implementation:

def fib (n: Long): Long = n match {
  case 0 | 1 => n
  case _ => fib( n - 2) + fib( n - 1 )
}

Now, this is inefficient (definitely not tail recursive) but it is very obvious how its structure relates to the Fibonacci sequence. We can make it properly tail recursive, though:

def fib (n: Long): Long = {
  def fibloop(current: Long, next: => Long, iteration: Long): Long = {
    if (n == iteration) 
      current
    else
      fibloop(next, current + next, iteration + 1)
  }
  fibloop(0, 1, 0)
}

That could have been written more tersely, but it is an efficient recursive implementation. That said, it is not as pretty as the first and it's structure is less clearly related to the original problem.

Finally, stolen shamelessly from elsewhere on this site is Luigi Plinge's streams-based implementation:

val fibs: Stream[Int] = 0 #:: fibs.scanLeft(1)(_ + _)

Very terse, efficient, elegant and (if you understand streams and lazy evaluation) very expressive. It is also, in fact, recursive; #:: is a recursive function, but one that operates in a lazily-evaluated context. You certainly have to be able to think recursively to come up with this kind of solution.

Iteration compared to For/While loops

I'm assuming you mean the traditional C-Style for, here.

Recursive solutions can often be preferable to while loops because C/C++/Java-style while loops do not return a value and require side effects to achieve anything (this is also true for C-Style for and Java-style foreach). Frankly, I often wish Scala had never implemented while (or had implemented it as syntactic sugar for something like Scheme's named let), because it allows classically-trained Java developers to keep doing things the way they always did. There are situations where a loop with side effects, which is what while gives you, is a more expressive way of achieving something but I had rather Java-fixated devs were forced to reach a little harder for it (e.g. by abusing a for comprehension).

Simply, traditional while and for make clunky imperative coding much too easy. If you don't care about that, why are you using Scala?

Efficiency and risk of Stackoverflow

Tail optimisation eliminates the risk of stackoverflow. Rewriting recursive solutions to be properly tail recursive can make them very ugly (particularly in any language running on the JVM).

Recursive solutions can be more efficient than more imperative solutions, sometimes suprisingly so. One reason is that they often operate on lists, in a way that only involves head and tail access. Head and tail operations on lists are actually faster than random access operations on more structured collections.

Dynamic Programming

A good recursive algorithm typically reduces a complex problem to a small set of simpler problems, picks one to solve and delegates the rest to another function (usually a recursive call to itself). Now, to me this sounds like a great fit for dynamic programming. Certainly, if I am trying a recursive approach to a problem, I often start with a naive solution which I know can't solve every case, see where it fails, add that pattern to the solution and iterate towards success.

The Little Schemer has many examples of this iterative approach to recursive programming, particularly because it re-uses earlier solutions as sub-components for later, more complex ones. I would say it is the epitome of the Dynamic Programming approach. (It is also one of the best-written educational books about software ever produced). I can recommend it, not least because it teaches you Scheme at the same time. If you really don't want to learn Scheme (why? why would you not?), it has been adapted for a few other languages

If versus Match

if expressions, in Scala, return values (which is very useful and why Scala has no need for a ternary operator). There is no reason to avoid simple

if (something)
  // do something
else
  // do something else

expressions. The principle reason to match instead of a simple if...else is to use the power of case statements to extract information from complex objects. Here is one example.

On the other hand, if...else if...else if...else is a terrible pattern

1. There's no easy way to see if you covered all the possibilities properly, even with a final else in place.
2. Unintentionally nested if expressions are hard to spot
3. It is too easy to link unrelated conditions together (accidentally or through bone-headed design)

Wherever you find you have written else if, look for an alternative. match is a good place to start.