The Fibonacci Sequence

We usually learn to implement the Fibonacci sequence in a language like Python in (at least) two ways:

def fib_recr(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib_recr(n - 1) + fib_recr(n - 2)

def fib_iter(n):
    cur, nxt = 0, 1
    for i in range(n):
        cur, nxt = (nxt, cur + nxt)
    return cur

Provide the equivalent implementations in OCaml. That is, implement the functions

val fib_recr : int -> int
val fib_iter : int -> int

so that fib_recr n and fib_iter n are the \(n\)^th Fibonacci number. The behavior of these functions is undefined if n is negative. Note that your implementation of fib_iter will not be iterative in the usual sense; rathe it should be tail recursive.

let _ = assert (fib_recr 8 = 21)
let _ = assert (fib_iter 8 = 21)