Haskell: Tail recursion

In this post, I am going to explain about the concept called tail recursion. This is a new concept, used to build recursive functions effectively in functional programming languages. As I said, Haskell don’t have loops, whatever you want to do, you should achieve using recursion. Most of the people think that recursion is inefficient, but that is not true. The efficiency of recursion is depending on the way you code it.

Simple Recursion example

Following snippet calculates the factorial of a number.

fact n = if (n==0) then 1 else n * fact (n-1)

I guess above code is self-explanatory. If n == 0, then it returns 1 (It is the base condition), else it return n * fact (n-1).

Prelude> let fact n = if (n==0) then 1 else n * fact (n-1)
Prelude> 
Prelude> fact 3
6
Prelude> fact 10
3628800
Prelude> fact 5
120

Programming languages maintain stack frames to keep track of recursive calls. Following step-by-step procedure explains that.

Step 1: fact(5) = 5 * fact(5-1) = 5 * fact (4)

Step 2: fact(5) =  5 * fact(4). To get the final result, we need to calculate fact(4).

 

Step 3: fact(4) = 4 * fact(3), to get the result of fact(4), we need to calculate fact(3) first.

Step 4: fact(3) = 3 * fact(2), to get the result of fact(3), we need to calculate fact(2) first.

Step 5: fact(2) = 2 * fact(1), to get the result of fact(2), we need to calculate fact(1) first.

Finally, we reached our base condition, fact(0) = 1.

fact(1) = 1 * fact(0) =  1 * 1 = 1

fact(2) = 2 * fact(1) =  2 * 1 = 2

fact(3) = 3 * fact(2) =  3 * 2 = 6

fact(4) = 4 * fact(3) =  4 * 6 = 24

fact(5) = 5 * fact(4) =  5 * 24 = 120

To calculate fact(5), We require 5 stack frames, So to calculate fact(1000000), we require 1000000 stack frames. Since stack is limited in size, you will end up in stack overflow error for large values, and also it impacts performance for large values.

Let me rewrite the same factorial program in other way.

Factorial.hs

fact :: Integer -> Integer
fact 0  = 1
fact n = let
             accumulator 0 temp = temp
             accumulator n temp = accumulator (n-1) (n*temp)
        in
            accumulator n 1

Prelude> :load Factorial.hs
[1 of 1] Compiling Main             ( Factorial.hs, interpreted )
Ok, modules loaded: Main.
*Main> 
*Main> fact 0
1
*Main> fact 5
120
*Main> fact 10
3628800
*Main>

let me try to explain, how this version of factorial works. What it does is, it calls a helper function ‘accumulator n 1’ that is locally defined. This helper function takes a number and also a variable temp, temp is used to maintain intermediate results.

fact (5) = accumulator 5 1

accumulator 5 1 =  accumulator (5-1) (5*1) = accumulator 4 5

accumulator 4 5 = accumulator (4-1) (4*5) = accumulator 3 20

accumulator 3 20 = accumulator (3-1) (3*20) = accumulator 2 60

accumulator 2 60 = accumulator (2-1) (2*60) = accumulator 1 120

accumulator 1 120 = accumulator (1-1) (1*120) = accumulator 0 120

accumulator 0 120 = 120

fact 5 = accumulator 5 1 = accumulator 4 5 = accumulator 3 20 = accumulator 2 60 = accumulator 1 120 = 120

Of course above function is also recursive, but here compiler can apply the optimization using tail recursion. Almost all functional languages apply this optimization. A tail call is a subroutine call performed as the final action of a procedure. If a tail call might lead to the same subroutine being called again later in the call chain, the subroutine is said to be tail-recursive, which is a special case of recursion. Compiler recognizes these kinds of tail recursive calls and treats them differently. Compiler uses the same stack frame for these kind of tail recursive calls, So one stack frame is enough to compute factorial of any number.

Previous                                                 Next                                                 Home