Fibonacci Series with recursion

Back to Programming


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,………………….


INPUT: The number of terms to be printed

OUTPUT: The terms of the Fibonacci Series.


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


                              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.



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.


The space complexity of this program is O(n) where n is the number of terms to be printed.