## Fibonacci Series with recursion

Back to Programming

### Description

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.

## SPACE COMPLEXITY:

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