(a)

The nth Tetranacci number T(n) is mathematically defined as follows.

T(0) = 0

T(1) = 1

T(2) = 1

T(3) = 2

T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4)

Write a tail recursive function tetra that computes the nth Tetranacci

number efficiently. In particular, large inputs such as (tetra 1000000)

should neither cause stackoverflow nor timeout.

start function with:

let tetra (n : int) : int =

(b)

Write a function that sums 2 natural numbers as represented by a list of integers between 0 and 9 where the head is the least signifigant digit. Your function should be tail recursive

sum [4; 3; 2; 1] [1;0;1] = [5; 3; 3; 1]

sum [1] [9;9;9] = [0; 0; 0; 1]

sum [] [] = []

sum (nines 1000000) [1] does not stack overflow, when (nines 1000000) provides a list of 1000000 9s

start the function with:

let rec sum (a : int list) (b : int list) : int list =