Generating Fibonacci Series using Recursion: C Program

Write a recursive function to obtain the first 25 numbers of a Fibonacci sequence. In a Fibonacci sequence the sum of two successive terms gives the third term. Following are the first few terms of the Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …

Note: In this video tutorial we’ve taken 0 and 1 as the first 2 numbers in the Fibonacci series- they’re called Seed Values. And we ask the user to enter the limit or the number of terms to be printed in the Fibonacci Series.

At the end of this article you can find C program source code which exactly matches the above problem statement. So if you’re only looking for exact solution to above problem statement, then directly scroll down to the end of this article and you can get the source code for it.

Related Read:
C Program To Generate Fibonacci Series using For Loop
Recursive Functions In C Programming Language

What Is Fibonacci Series?

Fibonacci Series is a series of numbers where the first two Fibonacci numbers are 0 and 1, and each subsequent number is the sum of the previous two. Its recurrence relation is given by F_n = F_n-1 + F_n-2.

Below we have series of Fibonacci numbers(10 terms):
0
1
1
2
3
5
8
13
21
34

How Its Formed:
0 <– First Number (n1)
1 <– Second Number (n2)
1 <– = 1 + 0 (1 and 0 are previous 2 terms)
2 <– = 1 + 1
3 <– = 2 + 1
5 <– = 3 + 2
8 <– = 5 + 3
13 <– = 8 + 5
21 <– = 13 + 8
34 <– = 21 + 13

Video Tutorial: Generating Fibonacci Series using Recursion: C Program

Source Code: C Program To Generate Fibonacci Series using Recursive Function

#include<stdio.h>

int fib(int);

int main()
{
    int limit, count;

    printf("Enter no of terms of Fibonacci Series to be printed\n");
    scanf("%d", &limit);

    for(count = 1; count <= limit; count++)
    {
        printf("\n%d. %d\n", count, fib(count));
    }

    return 0;
}

int fib(int num)
{
    if(num == 1)
        return(0);
    else if(num == 2 || num == 3)
        return(1);
    else
        return( fib(num-1) + fib(num-2) );
}

Output:
Enter no of terms of Fibonacci Series to be printed
8

1. 0

2. 1

3. 1

4. 2

5. 3

6. 5

7. 8

8. 13

Logic To Generate Fibonacci Series using For Loop

We ask the user to enter the limit or the number of terms he or she wants to print or display in the Fibonacci series. We store the user input number in a variable called limit.

We initialize the loop counter variable count to 1. Now we iterate the for loop from 1 to user input limit times. For each iteration we call the function fib() and pass the value present in the variable count. fib(count) gets the Fibonacci number for the count or nth term.

Inside fib() function
We know the first two terms in the Fibonacci series which are 0 and 1. To get the third term in this series we add 0 and 1. So the next term is 0+1 which is 1 once again. We’ll write separate conditions for this inside the fib() function.

If num is 1, we return 0. Which is the first term in the series. If num is 2 or 3, we return 1. Because 1 is the third as well as forth term in the series. If num is neither 1, nor 2 or 3, then we call the same function( fib() ) and pass the immediate preview 2 terms of the Fibonacci Series which are (num – 1) and (num -2), and add it to get the next term in the series.

fib(num-1) + fib(num-2)

This equation will keep calling itself and ultimately reduce to fib(1) or fib(2) or fib(3) for which we already know the values.

Example:

If user inputs a value of 5 to limit, then we need to print 5 terms in the Fibonacci Series. We write a for loop and iterate the loop from 1 to limit times. For each iteration of the for loop, loop counter value increments by 1. Inside for loop we call fin() method and pass the value present inside loop counter variable count. Through out the life cycle of the for loop, count will have value from 1 to 5. i.e., 1, 2, 3, 4, 5

For each iteration following code will be executed, and the returned value is printed out to the console window.

For fifth iteration fib(5) = fib(4) + fib(3) which follows the recurrence relation formula F(n) = F(n-1) + F(n-2).

Here fib(4) can be reduced to:
fib(4) = fib(4-1) + fib(4-2)
fib(4) = fib(3) + fib(2)

Now replace the value of fib(4) in below equation:

fib(5) = [fib(4)] + fib(3);
fib(5) = [fib(3) + fib(2)] + fib(3);

We already know that fib(2) and fib(3) are both equal to 1.

fib(5) = [1 + 1] + 1;
fib(5) = 2 + 1;
fib(5) = 3;

So the fifth term in the Fibonacci series is 3.

Source Code: Exact Solution For Above Problem Statement

#include<stdio.h>

int fib(int);

int main()
{
    int limit = 25, count;

    for(count = 1; count <= limit; count++)
    {
        printf("\n%d. %d\n", count, fib(count));
    }

    return 0;
}

int fib(int num)
{
    if(num == 1 || num == 2)
        return(1);
    else
        return( fib(num-1) + fib(num-2) );
}

Output:
1. 1

2. 1

3. 2

4. 3

5. 5

6. 8

7. 13

8. 21

9. 34

10. 55

11. 89

12. 144

13. 233

14. 377

15. 610

16. 987

17. 1597

18. 2584

19. 4181

20. 6765

21. 10946

22. 17711

23. 28657

24. 46368

25. 75025

Source Code: Generate 25 terms in Fibonacci Series using Recursion and Ternary/conditional operator

#include<stdio.h>

int fib(int);

int main()
{
    int limit = 25, count;

    for(count = 1; count <= limit; count++)
    {
        printf("\n%d. %d\n", count, fib(count));
    }

    return 0;
}

int fib(int num)
{
    return( (num == 1 || num == 2) ? 1 : ( fib(num-1) + fib(num-2) ) );
}

Output:
We get the same 25 terms in Fibonacci series as with above source code. Know more about ternary operator or conditional operator in a separate video tutorial: Ternary Operator / Conditional Operator In C

Disadvantages of using Recursion

Recursive Calls are not always efficient. Particularly in calculating Fibonacci Series – It’s better to use the regular iterative ways, instead of recursion. Recursion in this program creates lot of overhead for memory stack.

C Program To Generate Fibonacci Series using For Loop

Practice this program only as a way to learn the logic and working of recursion in C program.

For list of all c programming interviews / viva question and answers visit: C Programming Interview / Viva Q&A List

For full C programming language free video tutorial list visit:C Programming: Beginner To Advance To Expert