Convert recursive function to tail recursive function. Concept of tail recursion

Question

I am trying to convert some recursive functions in haskell. To get some experience with this type of functions i tried to understand the concept of tail-recursion. To get a clue i want to start with very easy functions to understand the concept behind tail-recursion. The following code shows a random recursive function i wrote. I want to convert it to a tail-recursive variant but i have problems using the theoretical concept on actual code.

h x = if x > 20 then 50 else x*x + h (x+1)

I'm no expert but I don't believe the concept of tail-recursion is that significant in Haskell, since Haskell doesn't have a "call stack" that recursive functions consume space from. (Converting recursive functions to being tail-recursive is very important in imperative languages, however, to avoid stack overflows.) — Robin Zigmond
– Robin Zigmond, Commented Apr 25, 2019 at 10:27
@RobinZigmond It's important in languages with tail-call optimization. Otherwise, tail recursion is no more efficient than regular recursion. — chepner
– chepner, Commented Apr 25, 2019 at 11:42
True @chepner, I realised after I wrote that that it's only significant in languages with TCO (why, Python, why?). But I figured that the point was clear enough even without that (important) technicality. — Robin Zigmond
– Robin Zigmond, Commented Apr 25, 2019 at 11:43
Python likes its stack traces more than efficient recursion, sadly. — chepner
– chepner, Commented Apr 25, 2019 at 11:48

sshine · Accepted Answer · 2019-04-26 11:43:52Z

2

As Robin Zigmond says, the concept of tail recursion doesn't apply in the same way in Haskell as it does in non-lazy languages. In languages with non-lazy semantics (so not Haskell), what you can do to achieve tail recursion is to move the expression that causes stack use to an accumulating argument like so:

h :: Int -> Int
h x = if x > 20 then 50 else x*x + h (x+1)

g :: Int -> Int
g z = g' z 50 where
  g' x y
    | x > 20 = y
    | otherwise = g' (x+1) (x*x + y)

Here the outer expression of the function body of g' is a call to itself, so if this were a non-lazy language, you wouldn't need to preserve the stack frames of old recursive calls before resolving the x*x + ... part of the expression. In Haskell this evaluates differently, though.

Comparing your h and this g in a micro-benchmark,

module Main where

import Criterion
import Criterion.Main

main :: IO ()
main = defaultMain [ bgroup "tail-recursion" [ bench "h" $ nf h 1
                                             , bench "g" $ nf g 1
                                             ]
                   ]

you actually get worse performance from this g':

benchmarking tail-recursion/h
time                 826.7 ns   (819.1 ns .. 834.7 ns)
                     0.993 R²   (0.988 R² .. 0.997 R²)
mean                 911.1 ns   (866.4 ns .. 971.9 ns)
std dev              197.7 ns   (149.3 ns .. 241.3 ns)

benchmarking tail-recursion/g
time                 1.742 μs   (1.730 μs .. 1.752 μs)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 1.742 μs   (1.729 μs .. 1.758 μs)
std dev              47.44 ns   (34.69 ns .. 66.29 ns)

You can get some of that performance back by making the arguments of g' strict,

{-# LANGUAGE BangPatterns #-}

g2 :: Int -> Int
g2 z = g' z 50 where
  g' !x !y
    | x > 20 = y
    | otherwise = g' (x+1) (x*x + y)

but it both looks and performs worse than the original h:

benchmarking tail-recursion/g2
time                 1.340 μs   (1.333 μs .. 1.349 μs)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 1.344 μs   (1.336 μs .. 1.355 μs)
std dev              33.40 ns   (24.71 ns .. 48.94 ns)

Edit: As K. A. Buhr pointed out, I forgot the -O2 flag for GHC; doing this provides the following micro-benchmark results:

h  time: 54.27 ns   (48.05 ns .. 61.24 ns)
g  time: 24.50 ns   (21.15 ns .. 27.35 ns)
g2 time: 25.47 ns   (22.19 ns .. 29.06 ns)

at which point the accumulating argument version does perform better and the BangPatterns version only performs as well, but both look worse than the original.

So a moral when trying to optimize code in general: Don't do it prematurely. And a moral when trying to optimize Haskell code in particular: You won't necessarily know that it matters until you try, and usually the most abstract solution that relies on library functions performs well.

edited Apr 26, 2019 at 11:43

answered Apr 25, 2019 at 11:03

sshine

16.2k1 gold badge45 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Napkin Over a year ago

Thank a lot. I tried some variations and found a very similar solution. So does the performance issue also apply to this variant of tail-recursion? hB x = hBHelp x 50 where hBHelp x y | x > 20 = y | otherwise = hBHelp (x+1) (x*x + y)

sshine Over a year ago

@Napkin: Yes, they're equivalent, but yours is nicer, so I substituted mine for it. You could give Criterion a try with stack install criterion. :-)

K. A. Buhr Over a year ago

Good answer, but it looks like your benchmarks might have been run without -O2. Compiling with GHC 8.6.4, I get similar results to yours without optimization, but with -O2 there's about a 20x speed-up and the tail recursive version actually beats out the non-tail recursive version for this particular example. Your advice still stands, though. It would be wrong to draw the conclusion that tail recursive versions will always (or even usually) be faster, and it would be a very bad idea to get into the habit of automatically writing code this way without performance testing.

Collectives™ on Stack Overflow

Convert recursive function to tail recursive function. Concept of tail recursion

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related