Efficient recursion in functional programming vs. inefficient recursion in different paradigms

Question

As far as I know recursion is very elegant but unefficient in OOP and procedural programming (see the wonderful "High Order perl", Mark Jason Dominus). I had some informations that in functional programming recursion is fast - keeping its elegance and simplicity. Could someone confirm and possibly amplify this? I am thinking in terms of XSLT and Haskell (high on my next-language-to-learn list)

Thanks

Daniel

Answer 1

Tail recursion is iteration in any decent functional language implementation. Here's an example using GHC Haskell. A simple program to add a sequence of numbers. It begins as the composition of several recursive functions:

import qualified Data.Vector as U

main = print (U.sum (U.enumFromTo 1 (10000000 :: Int)))

Which the compiler optimizes into a single tail recursive function (in a source-to-source transformation):

loop x y = case y <= y 10000000 of
      False -> x
      True  -> loop (x + y) (y + 1)

This recursive function is then compiled into a straight forward loop:

loop:
    .Lc216:
            cmpq $10000000,%rsi
            jle .Lc219
            movq %r14,%rbx
            movq (%rbp),%rax
            jmp *(%rax)
    .Lc219:
            addq %rsi,%r14
            incq %rsi
            jmp loop

Or with the GHC LLVM backend, additional optimizations are applied to the imperative representation of the program:

    loop:
        leaq    1(%rsi), %rax
        addq    %rsi, %r14
        cmpq    $10000001, %rax
        jge     .LBB1_5
        addq    $2, %rsi
        addq    %rax, %r14
    test:                                # %tailrecurse
        cmpq    $10000001, %rsi
        jl      loop

Note how the tail recursive label is tagged.

So we had a pipeline of recursive functions, which were compiled to a single tail recursive function, which was compiled to a single imperative loop using no stack. And 8 instructions in the end.

And that is why both function composition, and recursion, are extremely efficient in good, optimizing function languages.

Answer 2

OOP/Procedural languages tend to place data on the stack each time a recursive call is made - thus recursion is not as efficient as iteration in these languages.

By contrast, compilers/interpreters for functional languages are typically designed to optimize tail recursion to be as efficient as iteration:

Recursion may require maintaining a stack, but tail recursion can be recognized and optimized by a compiler into the same code used to implement iteration in imperative languages. The Scheme programming language standard requires implementations to recognize and optimize tail recursion. Tail recursion optimization can be implemented by transforming the program into continuation passing style during compilation, among other approaches.

what-is-tail-call-optimization and which-languages-support-tail-recursion-optimization have more detailed information.

Answer 3

If the compiler in use supports the tail call optimization and you structure your code to take advantage of it, recursion isn't inefficient.

Due to the prevelance of recursion in functional programming, compilers for functional languages are more likely to implement the tail call optimization that procedural ones.

Answer 4

Efficient recursion in XSLT

There are two main ways to achieve efficient recursion in XSLT:

1. Tail-recursion optimization
2. Divide and Conquer (DVC)

There are a lot of answers covering tail recursion, so here's just a simple example:

  <xsl:function name="my:sum">
   <xsl:param name="pAccum" as="xs:double*"/>
   <xsl:param name="pNums" as="xs:double*"/>

   <xsl:sequence select=
     "if(empty($pNums))
        then $pAccum
        else
           my:sum($pAccum + $pNums[1], $pNums[position() >1])
     "
   />
 </xsl:function>

One can check that my:sum(0, 1 to 100) is evaluated to: 5050.

Here is how one would implement the sum() function in a DVC way:

  <xsl:function name="my:sum2">
      <xsl:param name="pNums" as="xs:double*"/>

      <xsl:sequence select=
        "if(empty($pNums))
          then 0
          else
            if(count($pNums) eq 1)
              then $pNums[1]
              else
                for $half in count($pNums) idiv 2
                  return
                    my:sum2($pNums[not(position() gt $half)]) 
                   + 
                    my:sum2($pNums[position() gt $half])

        "
      />
  </xsl:function>

The main idea behind DVC is to subdivide the input sequence into two (usually) or more parts and to process them independently from one another, then to combine the results in order to produce the result for the total input sequence.

Note that for a sequence of N items, the maximum depth of the call stack at any point od time would not exceed log2(N), which is more than enough for most practical purposes. For example, the maximum depth of the call stack when processing a sequence of 1000000 (1M) items, would be only 19.

While there are some XSLT processors that are not smart enough to recognize and optimize tail-recursion, a DVC-recursive template works on any XSLT processor.

Answer 5

The only thing I have to add to dons's answer is that many language are hostage to legacy calling conventions. Nowhere is this more true than languages that conform to the C calling convention on x86: every parameter goes on the stack. Functional languages pass at least some parameters in registers, and so on the 32-bit platforms, even the non-tail calls (which can't be optimized) are still more efficient than in, say, C.

Thank God the x86-64 has a decent C calling convention!

Answer 6

If the language isn't optimized by the compiler, recursion is very likely to be slower than iteration, because on top of descending down given lane, which is pretty much equivalent to iteration, you have to backtrace your steps back to top upon finishing the job.

Otherwise, it is pretty much equivalent, except it may be much more elegant, as you let the compiler and system handle the loop behind the scenes. And of course there are tasks (like processing tree-like structures) where recursion is the only way (or at least the only that isn't hopelessly convoluted).

Answer 7

What makes recursion fast in functional languages is that compilers can internally transform recursion into iteration using tail recursion elimination (or more generally, tail call elimination). Basically, if a recursive call is the last operation before a function returns, and the function's return value is that of the recursive call, then instead of creating a new stack frame, the program will reuse the current frame. The argument variables are set to new values, and the PC is set to the beginning of the function.

Taking advantage of tail recursion elimination requires some awareness by the programmer. You need to make sure your recursive calls are actually tail calls. For instance, here is code in OCaml to compute a factorial:

let rec factorial n =
  if n = 0 then
    1
  else
    n * factorial (n - 1)

Tail call elimination would not directly work here since a multiplication has to be performed after the recursive call. However, if the function were rewritten as so:

let factorial n =
  let rec fac_helper n p =
    if n = 0 then
      p
    else
      fac_helper (n - 1) (p * n)
   in
   fac_helper n 1

Now tail call elimination can be used. This would get transformed to something like this (in pseudocode):

factorial p n = 
  p = 1
  while n > 0
    n = n - 1
    p = p * n
  return p

This style may seem counterintuitive, but it makes just as much sense as the iterative version. Each step of the computation is performed in a call to a recursive function. Induction variables such as p and n above, which are used over the whole computation, are declared as arguments.

It should be noted that most compilers for both imperative and functional languages take advantage of this optimization. In fact, LLVM's version of the optimization even allows associative operations between the recursive call and the return, so you could write the first version of factorial and still use the optimization. However, tail call elimination is not supported on the JVM so functional languages on the JVM like Scala have only limited support for it.

Answer 8

Don't assume that recursion vs. iteration is where you should place your concern.

Typically that becomes significant after you've first eliminated a series of larger performance issues.