C Program To Print Fibonacci Series Upto N Terms Using Recursion

Introduction

The Fibonacci sequence is a fascinating mathematical concept where each number is the sum of the two preceding ones, typically starting with 0 and 1. Recursion provides an elegant way to compute these numbers by defining a function that calls itself. In this article, you will learn how to write a C program to print the Fibonacci series up to n terms using a recursive approach.

Problem Statement

The challenge is to generate and display the first n terms of the Fibonacci sequence. For instance, if n is 7, the program should output the sequence: 0, 1, 1, 2, 3, 5, 8. The core requirement is to achieve this using a recursive function that calculates individual Fibonacci numbers.

Example

For an input of n = 7, the desired output is:

Fibonacci Series: 0 1 1 2 3 5 8

Background & Knowledge Prerequisites

To understand this article, readers should have a basic understanding of:

• C Programming Basics: Variables, data types, loops (for, while).
• Functions in C: How to define and call functions, pass arguments.
• Recursion: The concept of a function calling itself, base cases, and recursive steps.

Use Cases or Case Studies

The Fibonacci sequence, while simple in definition, appears in various contexts:

• Computer Science: Algorithms, data structures (e.g., Fibonacci heap), and even in the analysis of search algorithms.
• Nature: Explaining branching patterns in trees, the arrangement of leaves on a stem, the uncurling of a fern, and the spirals of a sunflower head.
• Art and Architecture: The golden ratio, closely related to the Fibonacci sequence, is often found in aesthetically pleasing designs.
• Financial Markets: Used in technical analysis for predicting price movements, known as Fibonacci retracement.
• Optimization Problems: Some dynamic programming problems leverage Fibonacci numbers or similar recursive patterns.

Solution Approaches

Recursive Approach to Fibonacci Series

This approach defines a function that calculates the nth Fibonacci number by recursively calling itself for the (n-1)th and (n-2)th numbers. The main program then iterates n times, calling this recursive function for each term to print the series.

One-line summary: Calculate each Fibonacci term by summing the two preceding terms using a recursive function, then loop to print the series.

Code Example:

// Fibonacci Series using Recursion
#include <stdio.h>

// Function to calculate the nth Fibonacci number recursively
int fibonacci(int n) {
    // Step 1: Define base cases for the recursion
    // If n is 0, the 0th Fibonacci number is 0
    if (n == 0) {
        return 0;
    } 
    // If n is 1, the 1st Fibonacci number is 1
    else if (n == 1) {
        return 1;
    } 
    // Step 2: Define the recursive step
    // For n > 1, the nth Fibonacci number is the sum of the (n-1)th and (n-2)th
    else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    int n, i;

    // Step 3: Prompt the user to enter the number of terms
    printf("Enter the number of terms for Fibonacci series: ");
    scanf("%d", &n);

    // Step 4: Validate the input
    if (n < 0) {
        printf("Please enter a non-negative integer.\\n");
        return 1; // Indicate an error
    }

    // Step 5: Print the series
    printf("Fibonacci Series: ");
    for (i = 0; i < n; i++) {
        printf("%d ", fibonacci(i)); // Call the recursive function for each term
    }
    printf("\\n");

    return 0; // Indicate successful execution
}

Run

Sample Output:

Enter the number of terms for Fibonacci series: 7
Fibonacci Series: 0 1 1 2 3 5 8

Enter the number of terms for Fibonacci series: 10
Fibonacci Series: 0 1 1 2 3 5 8 13 21 34

Stepwise Explanation:

1. fibonacci(int n) Function:

• This function is designed to return the nth Fibonacci number.
• Base Cases: It first checks for the two essential base cases that stop the recursion:
• If n is 0, it returns 0.
• If n is 1, it returns 1.
• Recursive Step: If n is greater than 1, the function recursively calls itself twice: once for n-1 and once for n-2. The results of these two calls are then summed and returned. This embodies the definition of the Fibonacci sequence.

1. main() Function:

• Input: It prompts the user to enter the desired number of terms (n) for the series.
• Input Validation: It checks if n is non-negative, as the Fibonacci sequence is typically defined for non-negative integers.
• Series Generation: A for loop runs from i = 0 up to n-1. In each iteration:
• It calls the fibonacci(i) function. This means for i=0, it calculates the 0th Fibonacci number; for i=1, the 1st, and so on, up to the (n-1)th Fibonacci number.
• The returned value from fibonacci(i) is then printed, followed by a space.
• Output Formatting: A newline character is printed at the end to ensure clean output.

This approach demonstrates the direct application of recursion to the Fibonacci definition, making the code quite intuitive to understand for those familiar with the concept.

Conclusion

Recursion offers an elegant and direct translation of the mathematical definition of the Fibonacci sequence into code. By defining clear base cases and a recursive step, we can generate the series efficiently. While this recursive method is simple and demonstrates a core computer science concept well, it can be computationally intensive for large values of n due to redundant calculations.

Summary

• The Fibonacci sequence starts with 0 and 1, where each subsequent number is the sum of the two preceding ones.
• Recursion involves a function calling itself, requiring base cases to prevent infinite loops.
• The fibonacci(n) recursive function has base cases fibonacci(0) = 0 and fibonacci(1) = 1.
• The recursive step is fibonacci(n) = fibonacci(n-1) + fibonacci(n-2).
• The main program iterates n times, calling the recursive function for each i to print the ith term.
• This recursive implementation is conceptually straightforward but can be inefficient for large n due to repeated computations of the same Fibonacci numbers.