FOR FREE YEAR SOLVED
Fibonacci Series with recursion
Back to ProgrammingDescription
Fibonacci series is a series of numbers in which each number is the sum of its two preceding numbers. The initial two values of the series are 0 and 1. From the 3rd term the values are found by adding the two preceding numbers and then the term is printed.
Here, the program is written to print the terms of the series using recursion. The number of terms to be printed is taken as input. The recursive function is called for each term of the series. The recursive function calculates the value of each term of the series and returns the value which is printed.
The first few Fibonacci numbers are:
0, 1, 1, 2, 3, 5, 8,………………….
Algorithm
INPUT: The number of terms to be printed
OUTPUT: The terms of the Fibonacci Series.
PROCESS:
Step 1: [Taking the input]
Read n [The number of terms to be printed]
Step 2: [Recursive function ‘fibo(n)’ which returns the nth term of the series]
If n = 0 then
Return 0
Else if n = 1
Return 1
Else
Return (fibo(n-1) + fibo(n-2) )
[End of ‘if’]
[End of function ‘fibo(n)’]
Step 3: [Calling the function ‘fibo(n)’ to print the fibonacci series]
Set a<-0
For i=1 to n repeat
Print fibo(a)
[Calling the function ‘fibo(n)’ to generate ath term and printing the term]
Set a<-a+1
[End of ‘for’ loop]
[End of printing the series]
Step 4: Stop.
Code
TIME COMPLEXITY:
The time complexity of finding the fibonacci number using recursion can be calculated as T(n) =T(n-1)+T(n-2). After solving this we get the complexity as O(2n) where n is the number of terms to be printed.
SPACE COMPLEXITY:
The space complexity of this program is O(n) where n is the number of terms to be printed.
