Fibonacci Number-Asked in Interviews
Problem Statement :
Write a program to find the nth number in the Fibonacci Series.
The input consists of only one line with input ’N’ signifying the nth number in the Fibonacci series.
The output consists of a line that contains the ‘N’th Fibonacci number.
Explanation of given Test Cases :
It is quite intuitive from the series that the 9th term in the fibonacci series is 34.
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(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
Time Complexity: Exponential
Space Complexity: O(n) if we consider the function call stack size, otherwise O(1).