A tail recursive function is one that performs a recursive call as its final step. Tail recursion is important because it can be more efficient - you can reuse the same stack frame for the next call, saving some time and memory. For example, a NON tail recursive Fibonacci function in OCaml (forgive me if I mess the syntax up any, most of the functional programming I've done is in Haskell): let rec fib n = match n with 0 -> 1 | 1 -> 1 | n -> fib (n - 1) + fib (n - 2) Obviously, the call to fib isn't the last thing that gets evaluated. That'd be the sum of the two recursive calls. Here's a tail recursive Fibonacci function, from Literate Programming Wiki: let fib n = let rec aux n b a = if n <= 0 then a else aux (n-1) (a+b) b in aux n 1 0 It works by "carrying along" the present sum as an argument in the aux function. That way, each call of aux can only make one recursive call (in the else branch), and the Fibonacci numbers are calculated as part of that recursive call.