Fibonacci Number-Asked in Interviews

Problem Statement :

Write a program to find the nth number in the Fibonacci Series.

Input Format

The input consists of only one line with input ’N’ signifying the nth number in the Fibonacci series.

Output Format:

The output consists of a line that contains the ‘N’th Fibonacci number.

Given:

9

Output:

34

Explanation of given Test Cases :

It is quite intuitive from the series that the 9th term in the fibonacci series is 34.

Approach:

Use recursion:

We first take ‘n’ as the input from the user. We then recursively call the function ‘fib’ with n as the parameter which in turn calls fib(n-1) and fib(n-2) until n becomes 1, at which point we return n.

                          fib(5)   
                     /                \
               fib(4)                fib(3)   
             /        \              /       \ 
         fib(3)      fib(2)         fib(2)   fib(1)
        /    \       /    \        /      \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /     \
fib(1) fib(0)

Code:

Time Complexity: Exponential
Space Complexity: O(n) if we consider the function call stack size, otherwise O(1).

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.