C program to find nth fibonacci term using recursion

Write a recursive function to generate n^th fibonacci term in C programming. How to generate n^th fibonacci term in C programming using recursion. Logic to find nth Fibonacci term using recursion in C programming.

Input any number: 10

10th Fibonacci term: 55

Required knowledge

Basic C programming, Functions, Recursion

Must know – Program to generate Fibonacci series using for loop

What is Fibonacci series?

Fibonacci series is a series of numbers where the current number is the sum of previous two terms. For Example: 0, 1, 1, 2, 3, 5, 8, 13, 21, … , (n-1th + n-2th)

Declare recursive function to find nth Fibonacci term

1. Assign a meaningful name to the function, say fibo().
2. The function accepts an integer hence update function declaration to fibo(int num).
3. Finally the function must return the n^th Fibonacci term which is an integer. Hence, return type of the function should be unsigned long long.

Function declaration to find n^th Fibonacci term is – unsigned long long fibo(int num);

Logic to find nth Fibonacci term using recursion

The recursive function to find n^th Fibonacci term is based on below three conditions.

1. If num == 0 then return 0. Since Fibonacci of 0^th term is 0.
2. If num == 1 then return 1. Since Fibonacci of 1^st term is 1.
3. If num > 1 then return fibo(num - 1) + fibo(n-2). Since Fibonacci of a term is sum of previous two terms.

Program to find nth Fibonacci term using recursion

/**
 * C program to find nth Fibonacci term using recursion
 */

#include <stdio.h>


/* Function declaration */
unsigned long long fibo(int num);


int main()
{
    int num;
    unsigned long long fibonacci;
    
    /* Input a number from user */
    printf("Enter any number to find nth fiboacci term: ");
    scanf("%d", &num);
    
    fibonacci = fibo(num); 
    
    printf("%d fibonacci term is %llu", num, fibonacci);
    
    return 0;
}


/**
 * Recursive function to find nth Fibonacci term
 */
unsigned long long fibo(int num) 
{
    if(num == 0)      //Base condition
        return 0;
    else if(num == 1) //Base condition
        return 1;
    else 
        return fibo(num-1) + fibo(num-2); 
}

Enter any number to find nth fiboacci term: 10
10 fibonacci term is 55

Note: Some compilers doesn’t supports unsigned long long type so you must replace it with unsigned long and format specifier to %lu to overcome the compilation error if any.

Happy coding 😉