# Issue

This Content is from Stack Overflow. Question asked by mxbr236

Currently I’m trying to convert different function from tail recursive to cps (continuation passing style) using OCaml language.

Normally, I managed to do a sum and factorial function:

Sum function:

Tail recursive:

``````let sum n =
let rec subSum n acc =
match n with
|0 -> acc
|_ -> subSum (n-1) (n+acc)
in subSum n 0;;

Printf.printf "%un" (sum 5);; (*returns 15*)
``````

cps version:

``````let sum2 n =
let rec sum_cps n acc =
match n with
|0 -> acc 0
|_ -> sum_cps (n-1) (fun r -> acc (n+r))
in sum_cps n (fun n -> n);;

Printf.printf "%un" (sum2 5);; (*returns 15*)
``````

factorial (same style as sum):

tail recursive:

``````let fact n =
let rec subFact n acc =
match n with
|0 -> acc
|1 -> acc
|_ -> subFact (n-1) (n*acc)
in subFact n 1;;

Printf.printf "%un" (fact 6);; (*returns 720*)
``````

cps version:

``````let fact2 n =
let rec fact_cps n acc =
match n with
|0 -> acc 1
|1 -> acc 1
|_ -> fact_cps (n-1) (fun r -> acc (n*r))
in fact_cps n (fun n -> n);;

Printf.printf "%un" (fact2 6);; (*returns 720*)
``````

However, in fibonacci, there is another argument in addition to the accumulator and that disturbs me a little bit:

tail recursive version:

``````let fibo n =
let rec fibon n acc prev =
match n with
|0 -> acc
|_ -> fibon (n-1) (prev+acc) acc
in fibon n 0 1;;

Printf.printf "%un" (fibo 6);; (*returns 8*)
``````

cps attempt (not working):

``````let fibo n =
let rec fibo_cps n acc prev =
match n with
|0 -> 0
|_ -> fibo_cps (n-1) (fun r -> acc (prev+r)) acc
in fibo_cps n (fun n -> n) 1L;;
``````

I would just like to understand how to make a working cps version of fibonacci.

# Solution

I think this is what you’re looking for –

``````let fibo n =
let rec fibo_cps n acc =
match n with
|0 -> acc 0
|1 -> acc 1
|_ -> fibo_cps (n-1) (fun x -> fibo_cps (n-2) (fun y -> acc (x+y)))
in fibo_cps n (fun x -> x)
``````

Please note that while the computation above is tail-recursive, it’s still a very inefficient way to compute fibonacci numbers. Consider a linear iterative algorithm –

``````let fibo2 n =
let rec aux n a b =
match n with
|0 -> a
|_ -> aux (n-1) b (a+b)
in aux n 0 1
``````

``` This Question was asked in  StackOverflow by  mxbr236 and Answered by Mulan It is licensed under the terms of
CC BY-SA 2.5. - CC BY-SA 3.0. - CC BY-SA 4.0.```