C program to get nth Fibonacci term using recursion

The Fibonacci sequence is a series of numbers where each number (after the first two) is the sum of the two preceding ones. The sequence starts with 0 and 1, and it continues indefinitely. The concept of Fibonacci numbers has applications in computer algorithms, mathematics, and even art and nature. In this article, we will explore how to write a C program to find the nth Fibonacci term using recursion. We'll cover the concept of the Fibonacci sequence, explain the recursive approach, and provide a complete C program with detailed explanations.

Understanding the Fibonacci Sequence

The Fibonacci sequence is defined as follows:

Where:

• F(0) and F(1) are the base cases, with values 0 and 1, respectively.
• F(n) is the nth Fibonacci number, which is the sum of the two preceding numbers F(n-1) and F(n-2).

Concept of Recursion

Recursion is a technique where a function calls itself to solve smaller instances of the same problem. In the case of the Fibonacci sequence, recursion is a natural fit because each term is defined in terms of previous terms.

Algorithm to Find the nth Fibonacci Term Using Recursion

1. Base Cases:
   • If n is 0, return 0.
   • If n is 1, return 1.
2. Recursive Case:
   • For n >= 2, return the sum of the two previous Fibonacci numbers: F(n-1) + F(n-2).

Write a C program to get nth Fibonacci term using recursion

Below is a C program to find the nth Fibonacci term using recursion:

#include <stdio.h>

// Recursive function to find the nth Fibonacci number
int fibonacci(int n) {
    // Base cases
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    // Recursive case
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n;

    // Input the term number from the user
    printf("Enter the term number to find in the Fibonacci series: ");
    scanf("%d", &n);

    // Ensure the term number is non-negative
    if (n < 0) {
        printf("Please enter a non-negative integer.");
    } else {
        // Calculate the nth Fibonacci number using the recursive function
        int result = fibonacci(n);
        // Output the result
        printf("The %dth Fibonacci number is %d.", n, result);
    }

    return 0;
}

Output

Enter the term number to find in the Fibonacci series: 5
The 5th Fibonacci number is 5.

Explanation of the Code

1. Recursive Function fibonacci:
   • This function takes an integer n as an argument and returns the nth Fibonacci number.
   • Base Cases: If n is 0, the function returns 0. If n is 1, it returns 1.
   • Recursive Case: For n >= 2, the function returns fibonacci(n - 1) + fibonacci(n - 2).
2. Main Function main:
   • The user is prompted to enter the term number n.
   • The function checks if n is non-negative, as the Fibonacci sequence is defined for non-negative integers only.
   • The fibonacci function is called with the user-provided term number, and the result is stored in the variable result.
   • The nth Fibonacci number is then printed.

Example Runs

Example 1

Enter the term number to find in the Fibonacci series: 5
The 5th Fibonacci number is 5.

Example 2

Enter the term number to find in the Fibonacci series: 10
The 10th Fibonacci number is 55.