CODEWITHSUNDEEP
haskellrecursionfibonaccireduction
user2426316
user2426316

Reputation: 7331

How does Haskell evaluate the Fibonacci function?

I am currently looking at this function in Haskell which returns the Fibonacci number at position n

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Now, it compiles, returns the correct result and everything... but I don't see how Haskell evaluates this function.

Doesn't Haskell always look for a suitable definition and then apply that definition until it cannot anymore (e.g. reached base case)?

In that case, this is what I came up with. For instance, evaluating fib 3

fib n = fib (n-1) + fib (n-2)
fib 3 = fib (3-1) + fib (3-2)
fib 3 = fib ((3-1)-1) + fib ((3-1)-2) + fib ((3-2)-1) + fib ((3-2)-2)
fib 3 = fib (((3-1)-1)-1) + fib (((3-1)-1)-2) +
        fib (((3-1)-2)-1) + fib (((3-1)-2)-2) + 
        fib (((3-2)-1)-1) + fib (((3-2)-1)-2) + 
        fib (((3-2)-2)-1) + fib (((3-2)-2)-2)
...

This could go on forever without giving an actual result. However, Haskell returns a result. So what am I doing wrong?

Upvotes: 0

Views: 300

Answers (1)

chi
chi

Reputation: 116139

The order of the equations in the definition does matter.

The part

fib n = fib (n-1) + fib (n-2)

gets applied only when the previous lines do not apply. That is, only when n is not 0 nor 1. Because of this, the step

fib 3 = fib (3-1) + fib (3-2)
fib 3 = fib ((3-1)-1) + fib ((3-1)-2) + fib ((3-2)-1) + fib ((3-2)-2)

is wrong: fib (3-2) is fib 1 = 1, and not fib ((3-2)-1) + fib ((3-2)-2).

Another way to look at is is as follows. The whole 3-lines definition can be equivalently expressed using case as

fib n = case n of
        0 -> 0
        1 -> 1
        m -> fib (m-1) + fib (m-2)

Upvotes: 4

Related Questions