2

I am a beginner in F#, and I am still having trouble wrapping my head around the concept of the tail recursion. Specifically, I do not know how tail recursion works since neither is there any value associated with the accumulator, nor is the accumulator ever defined.

Here is some sample code for a tail recursive function for computing a factorial

let factorial x =
// Keep track of both x and an accumulator value (acc)
    let rec tailRecursiveFactorial x acc =
        if x <= 1 then 
            acc
        else 
            tailRecursiveFactorial (x - 1) (acc * x)
    tailRecursiveFactorial x 1

I am not asking for how to write a tail recursive function, nor am I asking for examples of tail and non-tail recursive functions. What I am asking is how the accumulator works since it is never defined

Mark Seemann
  • 225,310
  • 48
  • 427
  • 736
Clement Decker
  • 137
  • 1
  • 6
  • Possible duplicate of [F# Tail Recursive Function Example](http://stackoverflow.com/questions/3248091/f-tail-recursive-function-example) – zarak Aug 11 '16 at 17:53
  • @ I am asking how the accumulator works if it is never defined, not for some examples of tail-recursive functions. – Clement Decker Aug 11 '16 at 18:00

1 Answers1

9

The accumulator is defined here:

let rec tailRecursiveFactorial x acc =

This local function has the type int -> int -> int, which means that acc has type int.

The compiler infers this because x is compared to the literal 1, which is of the type int, because it's an unqualified integer literal. This means x must be of the type int as well.

Likewise, the expression acc * x makes use of x, and the compiler then infers that acc must have the type int as well.

Mark Seemann
  • 225,310
  • 48
  • 427
  • 736
  • 1
    But how does the compiler know what the value of the accumulator is? – Clement Decker Aug 11 '16 at 18:10
  • 6
    @ClementDecker The value is assigned the literal `1` in the final expression: `tailRecursiveFactorial x 1`. – Mark Seemann Aug 11 '16 at 18:11
  • 1
    @ClementDecker also note you may want to change `x` to `n` in the first line and last line. As is, you have `x` referring to two different variables (the arg in `factorial` and the first arg to `tailRecursiveFactorial`) and it seems like it may be confusing you. – Dax Fohl Aug 12 '16 at 14:10