44

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.

dagnelies
  • 5,415
  • 3
  • 20
  • 26
marco-fiset
  • 8,721
  • 9
  • 35
  • 46
  • 10
    Case in point: many functional languages make heavy use of tail call optimization, while very few procedural languages do that. This means that tail call recursion is *much* cheaper in those functional languages. – Joachim Sauer May 18 '12 at 12:46
  • 7
    Actually, the Haskell definition you gave is pretty bad. `factorial n = product [1..n]` is more succinct, more efficient, and does not overflow the stack for large `n` (and if you need memoization, entirely different options are requires). `product` is defined in terms of some `fold`, which *is* defined recursively, but with extreme care. Recursion *is* an acceptable solution most of the time, but it's still easy to do it wrong/suboptimal. –  May 18 '12 at 12:53
  • 1
    @JoachimSauer - With a little embellishment, your comment would make a worthwhile answer. – Mark Booth May 18 '12 at 13:06
  • Your edit indicates you didn't catch my drift. The definition you gave is a perfect example of recursion which is bad *even in functional languages*. My alternative is also recursive (though it's in a library function) and *very* efficient, only how it recurses makes a difference. Haskell is also an odd case in that laziness breaks the usual rules (case in point: functions can overflow the stack while being tail recursive, and be very efficient without being tail recursive). –  May 18 '12 at 13:16
  • @delnan : Thanks for the clarification ! I'll edit my edit ;) – marco-fiset May 18 '12 at 13:18
  • Your imperative code could be collapsed to `x == 0 ? 1 : x * factorial(x - 1)`. – chrisaycock May 18 '12 at 13:43
  • @chrisaycock : It could, but I wanted to show the code as it is in the book. – marco-fiset May 18 '12 at 13:45
  • When you say "language" are you including compilers in the scope of discussion? ISTM that it's the popular implementations of functional languages which are better at recursion rather than the languages per se. – Peter Taylor May 18 '12 at 15:59
  • @PeterTaylor : I haven't thought about it, but yes, it is more a compiler issue than a language one. – marco-fiset May 18 '12 at 16:24

8 Answers8

39

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.

tdammers
  • 52,406
  • 14
  • 106
  • 154
18

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.

chrisaycock
  • 6,655
  • 3
  • 30
  • 54
  • I already know what pattern matching is all about and I think it is an awesome feature in Haskell that I miss in the languages I use! – marco-fiset May 18 '12 at 13:11
  • @marcof My point is that all the talk about recursion vs iteration doesn't address the sleekness of your code sample. It's really about pattern matching vs conditionals. Perhaps I should have put that up top in my answer. – chrisaycock May 18 '12 at 13:16
  • Yes, I understood that too :P – marco-fiset May 18 '12 at 13:21
  • @chrisaycock: Would it be possible to see iteration as tail recursion in which all the variables used in the loop body are both arguments and return values of the recursive calls? – Giorgio May 18 '12 at 16:11
  • @Giorgio: Yes, make your function take and return a tuple of the same type. – Ericson2314 Jun 21 '13 at 17:25
  • @Sonarpulse: The return type need not be the same as the input arguments. For example, a function computing the maximum in a list of integers may take an accumulator and a list as input, and return an int as result. – Giorgio Jun 21 '13 at 17:47
  • Oh, I see I misread your question. I thought you said something along the lines of "Would it be possible to recur where all the variables used in the loop body are both arguments and return values of the recursive calls?". I'm sorry. – Ericson2314 Jun 23 '13 at 02:07
5

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.

Telastyn
  • 108,850
  • 29
  • 239
  • 365
  • 1
    Re: 1. Early returns have *nothing* to do with tail calls. You can return early with a tail call, and have the "late" return also feature a tail call, and you can have a single simple expression with the recursive call *not* in a tail position (cf. OP's factorial definition). –  May 18 '12 at 13:18
  • @delnan: Thanks; it's early and it has been quite a while since I've studied the thing. – Telastyn May 18 '12 at 13:22
1

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)

Steven Evers
  • 28,200
  • 10
  • 75
  • 159
  • 1
    (1) Such optimization only applies in very specific cases - OP's example is not them, and many other straightforward functions need some extra care to become tail-recursive. (2) Real *tail-call* optimization does not only optimize recursive functions, it removes the space overhead from *any* call which is immediately followed by a return. –  May 18 '12 at 12:56
  • @delnan: (1) Yes, very true. In my 'original draft' of this answer, I had mentioned that :( (2) Yes, but within the context of the question, I thought that'd be extraneous to mention. – Steven Evers May 18 '12 at 13:01
  • Yes, (2) is just a useful addition (though indispensable for continuation-passing style), answers needn't mention is. –  May 18 '12 at 13:06
1

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.

Mert Akcakaya
  • 2,089
  • 1
  • 13
  • 16
  • 5
    Haskell is among the very few non-strict languages - the entire ML family (aside from some research spinoffs which *add* laziness), all popular Lisps, Erlang, etc. are all strict. Also, the second paragraphs seems off - as you correctly state in the first paragraph, laziness *does* allows infinite recursion (the Haskell prelude has the immensely useful `forever a = a >> forever a` for instance). –  May 18 '12 at 13:02
  • @deinan: As far as I know SML/NJ also offers lazy evaluation but it is an addition to SML. I also wanted to name two of the few lazy functional languages: Miranda and Clean. – Giorgio May 18 '12 at 16:18
1

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.

Bruce Ediger
  • 3,535
  • 16
  • 16
0

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)))
 )
)
K.Steff
  • 4,475
  • 2
  • 31
  • 28
0

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.

Karl Bielefeldt
  • 146,727
  • 38
  • 279
  • 479