Fibonacci Series

The Fibonacci series is a sequence of numbers in which each number is the sum of the two preceding ones.

The sequence typically starts with 0 and 1. The mathematical formula to calculate the fibonacci number is:

F(n) = F(n−1) + F(n−2)

Where:

F(0) = 0
F(1) = 1
For n>1, F(n) = F(n−1) + F(n−2)

This sequence is used in various fields like computer science, mathematics, and nature. It is called Fibonacci sequence after the Italian mathematician Leonardo of Pisa, known as Fibonacci, who introduced it to the western world in his book Liber Abaci.

Theory Behind Fibonacci Sequence

The Fibonacci sequence can be described as a recurrence relation where each term depends on the two previous terms. The sequence is defined recursively, which is why recursion is often used to compute Fibonacci numbers.

The recursive approach works by breaking down the problem into smaller subproblems and solving them individually.

Properties of Fibonacci Sequence:

Initial conditions: The first two Fibonacci numbers are defined explicitly as F(0) = 0 and F(1) = 1.

Recurrence relation: Every subsequent number is the sum of the two preceding ones: F(n) = F(n−1) + F(n−2) This recursive definition allows us to calculate Fibonacci numbers.

Growth rate: The Fibonacci sequence grows exponentially, and it is closely related to the golden ratio. As n increases, the ratio of consecutive Fibonacci numbers approaches the golden ratio (approximately 1.618).

Example of Fibonacci Series

Here’s how the Fibonacci series begins:

F(0) = 0, F(1) = 1

F(2) = F(1) + F(0) = 1+0 = 1

F(3) = F(2) + F(1) = 1+1 = 2

F(4) = F(3) + F(2) = 2+1 = 3

F(5) = F(4) + F(3) = 3+2 = 5

F(6) = F(5) + F(4) = 5+3 = 8

And so on...

So, the Fibonacci sequence starting from F(0) would be: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, .….

Fibonacci Series Using Recursion

The Fibonacci series can be computed using a recursive approach. In this approach, the function calls itself with smaller values of n until it reaches the base cases, F(0) and F(1).

Recursive Formula:

The recursive formula can be defined as:

Base Cases: F(0) = 0, F(1) = 1

Recursive Case: F(n) = F(n−1) + F(n−2)

C Program for Fibonacci Series Using Recursion

Here is an example of a simple C program to compute the n^th Fibonacci number using recursion:

#include <stdio.h>

// Recursive function to calculate Fibonacci number
int fibonacci(int n) {
    // Base case: return 0 for F(0) and 1 for F(1)
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }

    // Recursive case: F(n) = F(n-1) + F(n-2)
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n;

    // Ask the user to input the position of the Fibonacci number
    printf("Enter the position in the Fibonacci sequence: ");
    scanf("%d", &n);

    // Call the Fibonacci function and print the result
    printf("Fibonacci number at position %d is: %d\n", n, fibonacci(n));
    return 0;
}

Explanation of the Program:

Recursive Function: The function fibonacci() is defined recursively. The function checks if the input n is either 0 or 1 (base cases). If so, it returns 0 or 1 respectively.

Otherwise, it calculates F(n) by calling itself with the values n-1 and n-2 and summing them up.

Main Function: The program asks the user to input a number n (the position in the Fibonacci sequence), and it calculates and prints the Fibonacci number at that position using the recursive fibonacci() function.

Time Complexity of Fibonacci Using Recursion

The recursive solution for Fibonacci numbers is simple, but it is inefficient. The time complexity of the naive recursive algorithm is O(2ⁿ), as it repeatedly calculates the same Fibonacci values multiple times.

Each call branches into two new calls, leading to an exponential growth in the number of calls.

For example:

fibonacci(5) will call fibonacci(4) and fibonacci(3).
fibonacci(4) will call fibonacci(3) and fibonacci(2).
This results in overlapping sub-problems.

Recursion provides an elegant and simple way to compute the Fibonacci series. However, the naive recursive approach can be inefficient for large numbers due to redundant calculations.

Menu