Why isn't this tail-recursive?

Question

I'm working through the book Real-World Functional Programming, and I tried to come up with my own example of tail recursion before reading the book's example (listing 10.2, p. 265). The book's example works; mine causes a stack overflow.

I've found if I use a tuple argument or pre-calculate a + accum then mine will work. I want to understand why.

let rnd = new System.Random()
let test2 = List.init 1000000 (fun _ -> rnd.Next(-50, 51))

let rec sum2 list accum =
  match list with
  | [] -> accum
  | a::b -> sum2 b a + accum

let result = sum2 test2 0

printfn "%d" result

sepp2k sepp2k · Accepted Answer · 2012-02-14T14:04:27

sum2 b a + accum

Note that this is parsed as (sum2 b a) + accum, not sum2 b (a + accum).

So this calls sum2 b a. Then it takes the result of that call and adds accum to it. So the last expression evaluated is the addition, not the call to sum2. Thus the call to sum2 is not a tail call.

Why isn't this tail-recursive?

2 Answers