# What Is Fibonacci Series in Data Structure?

//

Heather Bennett

The Fibonacci series is a sequence of numbers in which each number is the sum of the two preceding ones. This series was introduced by Leonardo Fibonacci in his book Liber Abaci, published in 1202. The Fibonacci sequence begins with 0 and 1, and each subsequent number is the sum of the previous two numbers.

## How Does the Fibonacci Series Work?

To understand how the Fibonacci series works, let’s take a look at the first few numbers:

• 0
• 1
• 1
• 2
• 3
• 5
• 8

In this series, each number (starting from the third number) is obtained by adding the two preceding numbers. For example, to get the third number (1), we add the first two numbers (0 + 1 = 1). Similarly, to get the fourth number (2), we add the second and third numbers (1 + 1 = 2).

## The Importance of Fibonacci Series in Data Structure

The Fibonacci series has significant applications in various fields, including mathematics, computer science, and data structures. It provides a foundation for understanding more complex algorithms and data structures.

### Fibonacci Series in Recursive Algorithms

The recursive approach to finding Fibonacci numbers is one of the most common examples of recursion in computer science. In this approach, a function calls itself to calculate each number based on its previous two numbers.

This recursive algorithm can be implemented using a simple if-else statement:

``````
int fibonacci(int n) {
if (n <= 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
```
```

This algorithm calculates the Fibonacci number for a given index n. However, it has an exponential time complexity, which makes it inefficient for large values of n.

### Fibonacci Series in Dynamic Programming

To overcome the inefficiency of the recursive algorithm, dynamic programming can be used to store previously calculated Fibonacci numbers and avoid redundant calculations.

By using an array or a table to store the values of Fibonacci numbers, we can achieve a linear time complexity:

``````
int fibonacci(int n) {
int fib[n + 2];
fib = 0;
fib = 1;

for (int i = 2; i <= n; i++)
fib[i] = fib[i - 1] + fib[i - 2];

return fib[n];
}
```
```

## Conclusion

The Fibonacci series is a fundamental concept in mathematics and computer science. Understanding how it works and its applications in data structures can greatly enhance your problem-solving skills. Whether you're implementing recursive algorithms or using dynamic programming techniques, the Fibonacci series will continue to be a valuable tool in your programming journey.