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

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.

Answer 2

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 3

One of the main benefits of recursion is that it lets you create solutions without mutation. for following example, you have to calculate the sum of all the elements of a List.

One of the many ways to solve this problem is as below. The imperative solution to this problem uses for loop as shown:

    scala> var total = 0
    scala> for(f <- List(1,2,3)) { total += f }

And recursion solution would look like following:

   def total(xs: List[Int]): Int = xs match {
      case Nil => 0
      case x :: ys => x + total(ys)
}

The difference is that a recursive solution doesn’t use any mutable temporary variables by letting you break the problem into smaller pieces. Because Functional programming is all about writing side effect free programs it's always encourage to use recursion vs loops (that use mutating variables).

Head recursion is a traditional way of doing recursion, where you perform the recursive call first and then take the return value from the recursive function and calculate the result.

Generally when you call a function an entry is added to the call stack of a currently running thread. The downside is that the call stack has a defined size so quickly you may get StackOverflowError exception. This is why Java prefers to iterate rather than recurse. Because Scala runs on the JVM, Scala also suffers from this problem. But starting with Scala 2.8.1, Scala gets away this limitation by doing tail call optimization. you can do tail recursion in Scala.

To recap recursion is preferred way in functional programming to avoid using mutation and secondly tail recursion is supported in Scala so you don't get into StackOverFlow exceptions which you get in Java.

Hope this helps.

Answer 4

As for stack overflow, a lot of the time you can get away with it because of tail call elimination.

The reason scala and other function paradigms avoid for/while loops they are highly dependent on state and time. That makes it much harder to reason about complex "loops" in a formal and precise manor.

Answer 5

I'm assuming that, since you say "recursion" in your title, you also mean "recursion" in your question, and not "iteration" (which cannot be chosen "over for/while loops", because those are iterative :D).

You might be interested in reading Effective Scala, especially the section on control structures, which should mostly answer your question. In short:

Recursion isn't "better" than iteration. Often it is easier to write a recursive algorithm for a given problem, then it is to write an iterative algorithm (of course there are cases where the opposite applies). When "tail call optimization" can be applied to a problem, the compiler actually converts it to an iterative algorithm, thus making it impossible for a StackOverflow to happen, and without performance impact. You can read about tail call optimization in Effective Scala, too.

The main problem with your question is that it is very broad. There are many many resources available on functional programming, idiomatic scala, dynamic programming and so on, and no answer here on Stack Overflow would be able to cover all those topics. It'd be probably a good idea to just roam the interwebs for a while, and then come back with more concrete questions :)