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?
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 onloop
.Change
loop t acc + h
toloop t (acc + h)
in order that the function becomes tail-recursive.