Are functional languages better at recursion?

Question

TL;DR : Do functional languages handle recursion better than non-functional ones?

I am currently reading Code Complete 2. At some point in the book, the author warns us about recursion. He says it should be avoided when possible and that functions using recursion are generally less effective than a solution using loops. As an example, the author wrote a Java function using recursion to compute the factorial of a number like so (it may not be exactly the same since I do not have the book with me at the moment):

public int factorial(int x) {
    if (x <= 0)
        return 1;
    else
        return x * factorial(x - 1);
}

This is presented as a bad solution. However, in functional languages, using recursion is often the preferred way of doing things. For example, here is the factorial function in Haskell using recursion:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

And is widely accepted as a good solution. As I have seen, Haskell uses recursion very often, and I did not see anywhere that it is frowned upon.

So my question basically is:

• Do functional languages handle recursion better than non-functional ones?

EDIT : I am aware that the examples I used are not the best to illustrate my question. I just wanted to point out that Haskell (and functional languages in general) uses recursion much more often than non-functional languages.

Answer 1

Yes, they do, but not only because they can, but because they have to.

The key concept here is purity: a pure function is a function with no side effects and no state. Functional programming languages generally embrace purity for many reasons, such as reasoning about code and avoiding non-obvious dependencies. Some languages, most notably Haskell, even go so far as to allow only pure code; any side effects a program may have (such as performing I/O) are moved to a non-pure runtime, keeping the language itself pure.

Not having side effects means you can't have loop counters (because a loop counter would constitute mutable state, and modifying such state would be a side effect), so the most iterative a pure functional language can get is to iterate over a list (this operation is typically called foreach or map). Recursion, however, is a natural match with pure functional programming - no state is needed to recurse, except for the (read-only) function arguments and a (write-only) return value.

However, not having side effects also means that recursion can be implemented more efficiently, and the compiler can optimize it more aggressively. I haven't studied any such compiler in depth myself, but as far as I can tell, most functional programming languages' compilers perform tail call optimization, and some may even compile certain kinds of recursive constructs into loops behind the scenes.

Answer 2

You're comparing recursion vs iteration. Without tail-call elimination, iteration is indeed more efficient because there's no extra function call. Also, iteration can go on forever, whereas it is possible to run out of stack space from too many function calls.

However, iteration requires changing a counter. That means there must be a mutable variable, which is prohibited in a purely functional setting. So functional languages are specially designed to operate without the need for iteration, hence the streamlined function calls.

But none of that addresses why your code sample is so sleek. Your example demonstrates a different property, which is pattern matching. That's why the Haskell sample doesn't have explicit conditionals. In other words, it's not the streamlined recursion that makes your code small; it's the pattern matching.

Answer 3

Technically no, but practically yes.

Recursion is far more common when you're taking a functional approach to the problem. As such, languages designed to use a functional approach often include features that make recursion easier/better/less problematic. Off the top of my head, there are three common ones:

1. Tail Call Optimization. As pointed out by other posters, functional languages often require TCO.

2. Lazy Evaluation. Haskell (and a few other languages) is lazily evaluated. This delays the actual 'work' of a method until it is required. This tends to lead to more recursive data structures and by extension, recursive methods to work on them.

3. Immutability. The majority of stuff you work with in functional programming languages is immutable. This makes recursion easier because you don't have to concern yourself with the state of objects over time. You can't have a value changed out from underneath you for example. Also, many languages are designed to detect pure functions. Since pure functions have no side effects, the compiler has a lot more freedom about what order the functions run in and other optimizations.

None of these things are really specific to functional languages versus others, so they're not simply better because they're functional. But because they're functional, the design decisions made will tend towards these features because they're more useful (and their downsides less problematic) when programming functionally.

Answer 4

Haskell and other functional languages generally uses lazy evaluation. This feature lets you write non-ending recursive functions.

If you write a recursive function without defining a base case where recursion ends, you end up with having infinite calls to that function and stackoverflow.

Haskell also supports recursive function call optimizations. In Java each function call would stack up and cause overhead.

So yes, functional languages handle recursion better than others.

Answer 5

The only technical reason I know of is that some functional languages (and some imperative languages if I recall) have what's called tail call optimization which allow a recursive method to not increase the size of the stack with every recursive call (ie. the recursive call more-or-less replaces the current call on the stack).

Note, that this optimization doesn't work on any recursive call, only tail-call recursive methods (ie. methods that don't maintain state at the time of the recursive call)

Answer 6

You'll want to look at Garbage Collection is Fast, But a Stack is Faster, a paper about using what C programmers would think of as "heap" for the stack frames in compiled C. I believe the author tinkered with Gcc to do that. It's not a definite answer, but that might help you understand some of the issues with recursion.

The Alef programming language, which used to come along with Plan 9 from Bell Labs, had a "become" statement (See section 6.6.4 of this reference). It's a sort of explicit tail-call recursion optimization. The "but it uses up call stack!" argument against recursion could potentially be done away with.

Answer 7

TL;DR: Yes they do
Recursion is a key tool in functional programming and therefore a lot of work has been done on optimizing these calls. For example, R5RS requires (in the spec!) that all implementations handle unbound tail recursion calls without the programmer worrying about stack overflow. For comparison, by default the C compiler won't do even an obvious tail-call optimization (try a recursive reverse of a linked list) and after some calls, the program will terminate (The compiler will optimize, though, if you use -O2).

Of course, in programs that are horribly written, such as the famous fib example which is exponential, the compiler has little to no options to do its 'magic'. So care should be taken not to hinder the compiler efforts in optimization.

EDIT: By the fib example, I mean the following:

(define (fib n)
 (if (< n 3) 1 
  (+ (fib (- n 1)) (fib (- n 2)))
 )
)

Answer 8

Functional languages are better at two very specific kinds of recursion: tail recursion and infinite recursion. They are just as bad as other languages at other kinds of recursion, like your factorial example.

That's not to say there aren't algorithms that work well with regular recursion in both paradigms. For example, anything that requires a stack-like data structure anyway, like a depth-first tree search, is simplest to implement with recursion.

Recursion comes up more often with functional programming, but it is also way overused, especially by beginners or in tutorials for beginners, perhaps because most beginners to functional programming have used recursion before in imperative programming. There are other functional programming constructs, like list comprehensions, higher-order functions, and other operations on collections, that are usually much better suited conceptually, for style, for conciseness, for efficiency, and for ability to optimize.

For example, delnan's suggestion of factorial n = product [1..n] is not only more concise and easier to read, it's also highly parallelizable. Same for using a fold or reduce if your language doesn't happen to have a product already built in. Recursion is the solution of last resort for this problem. The main reason you see it solved recursively in tutorials is as a jumping off point before getting to better solutions, not as an example of a best practice.