How to generate the nth Fibonacci number in Haskell

Overview

A Fibonacci sequence is one in which any integer is the sum of its two preceding numbers. It begins with 0 and 1 and goes up to infinity. Following is the Fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … and so on.

Algorithm

The formula to compute the nth Fibonacci number is as follows:

Fn = Fn-1 + Fn-2

Code

Following is the implementation of the formula above in Haskell:

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
main = print(fib 8)

Explanation

  • Line 1: We define the condition F(0) = 0.
  • Line 2: We define the condition F(1) = 1.
  • Line 3: We implement the recursive expression of the algorithm. The name of the function is fib.
  • Line 5: We invoke the fib function with n as 8.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)