Why isn't this F# code tail-recursive?

Question

I'm looking at the code in the F# 'Tutorial' template that is provided with Visual Studio 2015 and I see this code; I'm wondering why the first function isn't tail-recursive; I think I understand it but want to confirm:

/// Computes the sum of a list of integers using recursion.
let rec sumList xs =
    match xs with
    | []    -> 0
    | y::ys -> y + sumList ys

/// Make the function tail recursive, using a helper function with a result accumulator
let rec private sumListTailRecHelper accumulator xs =
    match xs with
    | []    -> accumulator
    | y::ys -> sumListTailRecHelper (accumulator+y) ys

Is the first one not tail recursive in the because '+' is a function and its' two arguments are evaluated first? Therefore the actual order of evaluation would be: y, then sumList ys, then +? Whereas in the second case, the order of evaluation is: accumulator,y,+ then sumListTailRecHelper(..)?

Yes, that's correct. + in the first code sample is the last function evaluated in non-empty list branch — Petr

Michel Billaud Michel Billaud · Accepted Answer · 2015-08-04T12:48:39

A call is tail-recursive if there's nothing left to do after the recursive call returns. So the last call amounts to going back to the start of the function code, with modified parameters.

In the first function you still have to add y to the result.

Why isn't this F# code tail-recursive?

1 Answers