Take the 2-minute tour ×

As per the MSDN documentation, while writing recursive function, The use of the accumulator argument makes the function tail recursive, which saves stack space. I'm using two example given on the MSDN site to calculate of sum of all the numbers in a list-

first without tail recursion-

let rec Sum myList =
    match myList with
    | [] -> 0
    | h::t -> h + Sum t

and now with tail recursion-

let Sumtail list =
    let rec loop list acc =
        match list with
        | h::t -> loop t acc + h
        | [] -> acc
    loop list 0

and running both the functions with input [1..100000]. Function Sum successfully calculates the sum of this list but gives stackoverflow exception if I pass [1..1000000] but the second function Sumtail fails at [1..100000] while it should give better performance then the first function since it uses tail recursion. Are there any other factors which affects the recursive function?

share|improve this question
I believe that you're misunderstanding something--the use of an accumulator argument doesn't make a function tail-recursive. An accumulator argument is a technique for accumulating values when one is using a tail-recursive function. It's sort of a technique that usually comes up with tail-recursive but it doesn't define tail-recursive. –  Onorio Catenacci Apr 11 '12 at 13:30

1 Answer 1

up vote 10 down vote accepted

Your second function isn't tail-recursive since loop t acc + h is parsed as (loop t acc) + h which makes + become the last operation on loop.

Change loop t acc + h to loop t (acc + h) in order that the function becomes tail-recursive.

share|improve this answer
thats right but I can't mark it right ans (still 6 mins to go). What diff does that make ? –  Kapilg Apr 11 '12 at 12:28
The '+' operator has to be applied to a return value from loop, so the compiler can't use tail recursion which would forget the state of h for each recursive call. Tail recursion works if the state can be forgotten - if we know that the return value would otherwise be returned through all the stack frames unmodified. –  uosɐſ Apr 11 '12 at 12:37

Your Answer


