Tail recursion.md

fib.hs

fib :: Int -> Int
fib n | n <= 0 = error "fib must over 0"
fib n | n == 1 = 1
fib n = tailFib n 0 1 

tailFib :: Int -> Int -> Int -> Int
tailFib n b a | n == 1 = a
tailFib n b a = tailFib (n - 1) a (a + b)

main = do 
    print (fib 10)

Tail recursion.md

Tail recursion

a. Write a tail-recursive version of the upto function mentioned in the lecture note, call it tailUpto :: Int->Int->[Int]->[Int]. For examples:

tailUpto 3 8 [1,2] = [3,4,5,6,7,8,1,2]
tailUpto 8 3 [1] = [1]

In other words, upto m n = tailUpto m n [].

b. Write a tail-recursive version of the fib function to compute the nth number in the Fibonacci sequence. Specifically, define the tailFib function with two accumulating parameters

tailFib :: Int->Int->Int->Int

so that fib n = tailFib n 0 1.

upto.hs

upto :: Int -> Int -> [Int]
upto m n = tailUpto m n []

tailUpto :: Int -> Int -> [Int] -> [Int]
tailUpto m n xs | m > n = xs
tailUpto m n xs = m : (tailUpto (m+1) n xs)

main = do
    print (upto 1 4)