How to make this simple recurrence relationship (difference equation) tail recursive?

Question

let rec f n =
    match n with
    | 0 | 1 | 2 -> 1
    | _ -> f (n - 2) + f (n - 3)

Without CPS or Memoization, how could it be made tail recursive?

Answer 1

let f n = Seq.unfold (fun (x, y, z) -> Some(x, (y, z, x + y))) (1I, 1I, 1I)
          |> Seq.nth n

Or even nicer:

let lambda (x, y, z) = x, (y, z, x + y)
let combinator = Seq.unfold (lambda >> Some) (1I, 1I, 1I)
let f n = combinator |> Seq.nth n

To get what's going on here, refer this snippet. It defines Fibonacci algorithm, and yours is very similar.

UPD There are three components here:

1. The lambda which gets i-th element;
2. The combinator which runs recursion over i; and
3. The wrapper that initiates the whole run and then picks up the value (from a triple, like in @Tomas' code).

You have asked for a tail-recursive code, and there are actually two ways for that: make your own combinator, like @Tomas did, or utilize the existing one, Seq.unfold, which is certainly tail-recursive. I preferred the second approach as I can split the entire code into a group of let statements.

Answer 2

The solution by @bytebuster is nice, but he does not explain how he created it, so it will only help if you're solving this specific problem. By the way, your formula looks a bit like Fibonacci (but not quite) which can be calculated analytically without any looping (even without looping hidden in Seq.unfold).

You started with the following function:

let rec f0 n = 
  match n with 
  | 0 | 1 | 2 -> 1 
  | _ -> f0 (n - 2) + f0 (n - 3) 

The function calls f0 for arguments n - 2 and n - 3, so we need to know these values. The trick is to use dynamic programming (which can be done using memoization), but since you did not want to use memoization, we can write that by hand.

We can write f1 n which returns a three-element tuple with the current and two past values values of f0. This means f1 n = (f0 (n - 2), f0 (n - 1), f0 n):

let rec f1 n = 
  match n with 
  | 0 -> (0, 0, 1)
  | 1 -> (0, 1, 1)
  | 2 -> (1, 1, 1)
  | _ -> 
    // Here we call `f1 (n - 1)` so we get values
    //   f0 (n - 3), f0 (n - 2), f0 (n - 1)
    let fm3, fm2, fm1 = (f1 (n - 1))
    (fm2, fm1, fm2 + fm3)

This function is not tail recurisve, but it only calls itself recursively once, which means that we can use the accumulator parameter pattern:

let f2 n =
  let rec loop (fm3, fm2, fm1) n = 
    match n with 
    | 2 -> (fm3, fm2, fm1)
    | _ -> loop (fm2, fm1, fm2 + fm3) (n - 1)
  match n with
  | 0 -> (0, 0, 1)
  | 1 -> (0, 1, 1)
  | n -> loop (1, 1, 1) n

We need to handle arguments 0 and 1 specially in the body of fc. For any other input, we start with initial three values (that is (f0 0, f0 1, f0 2) = (1, 1, 1)) and then loop n-times performing the given recursive step until we reach 2. The recursive loop function is what @bytebuster's solution implements using Seq.unfold.

So, there is a tail-recursive version of your function, but only because we could simply keep the past three values in a tuple. In general, this might not be possible if the code that calculates which previous values you need does something more complicated.