C program to find nth fibonacci term using recursion

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

Example

Input

Input any number: 10

Output

10th Fibonacci term: 55

Find nth fibonacci series using recursion

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 nth Fibonacci term which is an integer. Hence, return type of the function should be unsigned long long.

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

Logic to find nth Fibonacci term using recursion

Recursive function to find fibonacci series
The recursive function to find nth Fibonacci term is based on below three conditions.

  1. If num == 0 then return 0. Since Fibonacci of 0th term is 0.
  2. If num == 1 then return 1. Since Fibonacci of 1st 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); 
}

Output

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 😉