Haskell tail recursion for Fibonacci sequence-CodePudding

So I am working on an assignment where I have to find the nth fibonacci number, and I came across this idea shown below, however this returns a list, and I would just like to return the final number, so for example fibo 3 would give me [0,1,1,2,3,5,8,13], except I just want 13 to return, is there any way I could do that? This is my first time using Haskell and I am sort of learning functional programming as well for the first time, any help is appreciated. Thanks

fibo :: Integral x => x -> [x]
fibo n = fiboHelper [0,1] 0 1 n
fiboHelper :: Integral x => [x]->x->x->x->[x]
fiboHelper l x y 0 = l
fiboHelper l x y n = fiboHelper (l    [y x]    [y x y]) (x y) (y x y) (n-1)

CodePudding user response：

You can work with a helper function that contains two variables: the first and second item, and each

fibo :: (Integral a, Integral b) => a -> b
fibo 0 = 0
fibo n = fiboHelper 0 1 (n-1)

fiboHelper :: (Integral a, Integral b) => a -> a -> b -> a
fiboHelper si si1 n
    | n <= 0 = si1
    | otherwise = fiboHelper si1 (si si1) (n-1)

This then produces:

Prelude> fibo 7
13

As for the algorithm in your question, usually appending at the right side of a list is not a good idea, since it runs in linear time with the size of the left operand. This thus means that your algorithm runs in O(n²) time. You can implement this as:

fibo :: (Integral a, Integral b) => a -> [b]
fibo 0 = [0]
fibo n = 0 : fiboHelper 0 1 (n-1)

fiboHelper :: (Integral a, Integral b) => a -> a -> b -> [a]
fiboHelper si si1 n
  | n < 0 = []
  | otherwise = si1 : fiboHelper si1 (si si1) (n-1)

this will produce:

Prelude> fibo 7
[0,1,1,2,3,5,8,13]

CodePudding user response：

Instead of a list, you only need to keep track of the last two Fibonacci numbers, so that you can add them together for the next iteration. The recurrence relation you want can be defined using

-- replace a and b with (a b) and a, respectively, forgetting b.
helper a b n == fiboHelper (a b) a (n-1)
helper a b 1 == a
helper _ b 0 == b

(The second case isn't strictly necessary, but avoids an unnecessary addition.)

As n gets smaller, the desired value "accumulates" in the second parameter, with the value when n == 0 being the final result.

Note that you can get different series by providing different initial values for a and b. For example, fibo = helper 1 0, while the Lucas numbers are defined by lucas = helper 1 2:

lucas 5 = helper 1 2 5
        == helper 3 1 4
        == helper 4 3 3
        == helper 7 4 2
        == helper 11 7 1
(       == helper 18 11 0)
        == 11

CodePudding user response：

Yes, you can keep track of the last 2 steps as you go down the recursive stack.

fibo :: Integral x => x -> x
fibo a
  | a < 3      = 1
  | otherwise  = go 2 1 1 where
    go a' b' c'
       | a' == a    = c'
       | otherwise  = go (a' 1) (c') (b' c')

On a side note, a very interesting way I learned to create an infinite list of Fibonacci numbers in Haskell is as follows:

fibs = 1 : scanl ( ) 1 fibs

combining this with take and last you can achieve whatever solution you are looking for.

take 5 fibs
-- produces [1,1,2,3,5]

last $ take 5 fibs
-- produces 5