Fibonacci Series Using Recursion

The Fibonacci series is a well-known sequence of numbers in which each number is obtained by adding the two preceding numbers. It is one of the most important examples used to understand recursion in computer science.

The sequence usually starts with 0 and 1, and continues as:

• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Mathematical Definition

The Fibonacci sequence is defined using a recurrence relation:

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

With initial conditions:

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

Theory Behind Fibonacci Sequence

The Fibonacci sequence is based on the concept of a recurrence relation, where each term depends on previous terms. This makes it a natural fit for recursive programming.

• Each number is formed from the sum of the two previous numbers.
• The problem can be broken into smaller subproblems.
• Recursion is commonly used to implement it.

Important Properties

• Initial Conditions
  • F(0) = 0
  • F(1) =1
• Recurrence Relation
  • Each term depends on the previous two terms.
• Growth Pattern
  • The sequence grows rapidly in an exponential manner.
  • The ratio of consecutive terms approaches the golden ratio (~1.618).

Step-by-Step Example of Fibonacci Series

The first few Fibonacci numbers are calculated as:

• F(0) = 0
• F(1) = 1
• F(2) = 1 + 0
• F(3) = 1 + 1 = 2
• F(4) = 2 + 1 = 3
• F(5) = 3 + 2 = 5
• F(6) = 5 + 3 = 8

So the sequence becomes: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Fibonacci Series Using Recursion

Recursion is a natural way to compute Fibonacci numbers because the definition itself is recursive.

Recursive Idea

• Break the problem into smaller parts:
  • Compute F(n−1)
  • Compute F(n−2) 
• Combine both results to get F(n)

Recursive Formula

• Base Cases:
  • F(0) = 0
  • F(1) = 1
• Recursive Case: F(n) = F(n−1) + F (n − 2) 

C Program for Fibonacci Using Recursion

#include <stdio.h>

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

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

int main() {
    int n;

    printf("Enter the position in the Fibonacci sequence: ");
    scanf("%d", &n);

    printf("Fibonacci number at position %d is: %d\n", n, fibonacci(n));

    return 0;
}

Explanation of the Program

The program consists of two main parts:

1. Recursive Function (fibonacci)

• Checks base cases:
  • If n = 0, return 0
  • If n = 1, return 1
• Otherwise: Calls itself twice:
  • fibonacci(n − 1)
  • fibonacci( n− 2)
• Adds both results to compute the final value.

This shows how recursion breaks a problem into smaller subproblems.

2. Main Function

• Takes input from the user
• Calls the recursive function
• Displays the Fibonacci number at position nnn

Time Complexity of Recursive Fibonacci

Although recursion is simple and elegant, it is not efficient.

Time Complexity : O(2n)

Why It Is Inefficient

• Each call generates two more calls
• Many values are computed repeatedly
• This leads to overlapping subproblems

Example of Overlapping Calls

• fibonacci(5) calls: fibonacci(4), fibonacci(3)
• fibonacci(4) again calls: fibonacci(3), fibonacci(2)

Notice that the same values are recalculated multiple times.

Conclusion

The Fibonacci series is an important example of recursion because it directly follows a recursive definition.

• It is simple to understand and implement
• Clearly demonstrates recursive problem-solving

However:

• It has exponential time complexity
• Not suitable for large inputs without optimization

Better approaches like Dynamic Programming are used in real applications to improve performance.