Find the Nth Fibonacci Number

Given a number N, the task is to find N^th Fibonacci number.

The Fibonacci numbers are the numbers in the following integer series.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, .......

In this series, each number is the sum of the two preceding ones starting from 0 and 1.

Examples:

Input : N = 5
Output : 5

Input : N = 9
Output : 34

Method 1: Using loop
We know that, In Fibonacci series each number is the sum of the two preceding ones. So we can get N^th term by adding N- 1^th and N – 2^th term.
If we start from first two term of Fibonacci series (i.e 0 and 1) and keep adding preceding ones to get the next term we can reach to N^th term.

Below is the implementation of above approach:

// Scala program to calculate
// Nth term of Fibonacci series

// Creating Object
object W3Colleges {

  // Function to calculate 
  // the Nth term of Fibonacci series
  def fib(N: Int): Int = {
    var first = 0
    var second = 1
    var count = 0

    while (count < N) {
      val next = first + second
      first = second
      second = next
      count += 1
    }

    first
  }

  // Driver Code 
  def main(args: Array[String]): Unit = { 
    val N = 9
    println(fib(N))
  } 
}

Output:

Method 2: using Recursive formula
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

F₀ = 0, F₁ = 1
And, 
F_n = F_{n - 1} + F_{n - 2} for N > 1

Using above recurrence relation we can find N^th Fibonacci number.

Below is the implementation of above approach:

// Scala program to calculate
// Nth term of Fibonacci series using recursion

// Creating Object
object W3Colleges {

  // Function to calculate 
  // the Nth term of Fibonacci series
  // using recursion
  def fib(N: Int): Int = {
    if (N <= 1) 
      N 
    else 
      fib(N - 1) + fib(N - 2)
  }

  // Driver Code 
  def main(args: Array[String]): Unit = { 
    val N = 9
    println(fib(N))
  }
}

Output: