The Generalized Fibonacci Sequence
The Fibonacci sequence is defined by the following recurrence relation.
\begin{equation*} F_k = \begin{cases} k & k < 2 \\ F_{k - 1} + F_{k - 2} & k \geq 2 \end{cases} \end{equation*}This sequence can be generalized as follows. Given a list of starting values \(l\) of length \(n\), we define the sequence
\begin{equation*} G^l_k = \begin{cases} l[i] & i < n \\ \sum_{i = 1}^{n} G^l_{k - i} & i \geq n \end{cases} \end{equation*}
This is exactly the Fibonacci sequence when \(l\) is [0; 1].
Implement the function
val gen_fib : int list -> int -> int
So that gen_fib l k is \(G^l_k\) as defined above. The behavior of
the function is undefined if \(l\) is empty or \(k\) is negative. Your
solution must be tail recursive, and the running time of your
implementation must by independent of the length of the input list,
asymptotically.
Examples
let _ = assert (gen_fib [0; 1] 8 = 21)