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 Fn = Fn-1 + Fn-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


[youtube https://www.youtube.com/watch?v=cyi7QLlc_aE]

YouTube Link: https://www.youtube.com/watch?v=cyi7QLlc_aE [Watch the Video In Full Screen.]


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.

num or count fib() Output
1fib(1)0
2fib(2)1
3fib(3)1
4fib(4) = fib(3) + fib(2) 2
5fib(5) = fib(4) + fib(3) 3

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

C Program To Generate Fibonacci Series using Function

Lets write a C program to generate Fibonacci Series using function / method.

Related Read:
Fibonacci Series using While loop: C Program
C Program To Generate Fibonacci Series using For Loop

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 Fn = Fn-1 + Fn-2.

Below are a series of Fibonacci numbers(10 numbers):
0
1
1
2
3
5
8
13
21
34

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

Video Tutorial: C Program To Generate Fibonacci Series using Function


[youtube https://www.youtube.com/watch?v=R3MPbqvYooA]

YouTube Link: https://www.youtube.com/watch?v=R3MPbqvYooA [Watch the Video In Full Screen.]


Source Code: C Program To Generate Fibonacci Series using Function

#include<stdio.h>

void fibonacci(int);

int main()
{
    int limit;

    printf("Enter the number of terms to be printed\n");
    scanf("%d", &limit);

    fibonacci(limit);

    return 0;
}

void fibonacci(int num)
{
    int n1 = 0, n2 = 1, n3, count;

    printf("\nFibonacci Series ..\n");
    printf("1. %d\n2. %d\n", n1, n2);

    for(count = 3; count <= num; count++)
    {
        n3 = n1 + n2;
        printf("%d. %d\n", count, n3);

        n1 = n2;
        n2 = n3;
    }
}

Output 1:
Enter the number of terms to be printed
5

Fibonacci Series ..
1. 0
2. 1
3. 1
4. 2
5. 3

Output 2:
Enter the number of terms to be printed
14

Fibonacci Series ..
1. 0
2. 1
3. 1
4. 2
5. 3
6. 5
7. 8
8. 13
9. 21
10. 34
11. 55
12. 89
13. 144
14. 233

Logic To Generate Fibonacci Series using Function

We ask the user to enter the limit i.e., how many terms in the Fibonacci series to be printed. We pass this user entered limit to function fibonacci.

Inside fibonacci function
We initialize n1 to 0 and n2 to 1 and display it to the console. We do this because we know that in any Fibonacci series the first two numbers are 0 and 1.

Now we add n1 and n2 and assign it to n3, and display the value of n3 – which is the next number in the Fibonacci series. We use for loop to keep printing the Fibonacci series until the limit entered by the user.

Note: Function fibonacci takes 1 integer type argument and doesn’t return anything, so its return type is void.

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

C Program To Generate Fibonacci Series using For Loop

Lets write a C program to generate Fibonacci Series, using for loop.

Related Read:
Fibonacci Series using While loop: C Program

First Thing First: 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 Fn = Fn-1 + Fn-2.

Below are a series of Fibonacci numbers(10 numbers):
0
1
1
2
3
5
8
13
21
34

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

Video Tutorial: C Program To Generate Fibonacci Series using For Loop


[youtube https://www.youtube.com/watch?v=8VJVcwuYDPw]

YouTube Link: https://www.youtube.com/watch?v=8VJVcwuYDPw [Watch the Video In Full Screen.]


Source Code: C Program To Generate Fibonacci Series using For Loop

#include<stdio.h>

int main()
{
    int n1 = 0, n2 = 1, n3, count, num;

    printf("Enter the number of terms to be printed\n");
    scanf("%d", &num);

    printf("\n%d\n%d\n", n1, n2);

    for(count = 3; count <= num; count++)
    {
        n3 = n1 + n2;
        printf("%d\n", n3);

        n1 = n2;
        n2 = n3;
    }

    return 0;
}

Output:
Enter the number of terms to be printed
10

0
1
1
2
3
5
8
13
21
34

Logic To Generate Fibonacci Series using For Loop

We know that the first 2 digits in Fibonacci series are 0 and 1. So we directly initialize n1 and n2 to 0 and 1 respectively and print that out before getting into For loop logic. Since we’ve already printed two Fibonacci numbers, we assign 3 to loop control variable count and iterate through the for loop till count is less than or equal to the user entered number.

Inside For loop
As per definition of Fibonacci series: “..each subsequent number is the sum of the previous two.” So we add n1 and n2 and assign the result to n3 and display the value of n3 to the console.

Next, we step forward to get next Fibonacci number in the series, so we step forward by assigning n2 value to n1 and n3 value to n2.

For loop keeps repeating above steps until the count is less than or equal to the user entered number. If the user entered limit/count is 10, then the loop executes 8 times(as we already printed the first two numbers in the Fibonacci series, that is, 0 and 1).

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

Fibonacci Series using While loop: C Program

Today lets see how to generate Fibonacci Series using while loop in C programming.

First Thing First: 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 Fn = Fn-1 + Fn-2.

Below are a series of Fibonacci numbers(10 numbers):
0
1
1
2
3
5
8
13
21
34

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

Generate Fibonacci Series using While loop: C Program


[youtube https://www.youtube.com/watch?v=LhM2pvYwMDs]

YouTube Link: https://www.youtube.com/watch?v=LhM2pvYwMDs [Watch the Video In Full Screen.]


Source Code: Fibonacci Series using While loop: C Program

#include < stdio.h >

int main()
{
    int n1 = 0, n2 = 1, n3, count;

    printf("Enter the limit\n");
    scanf("%d", &count);

    printf("\n%d\n%d\n", n1, n2);

    count = count - 2;

    while(count)
    {
        n3 = n1 + n2;
        printf("%d\n", n3);
        n1 = n2;
        n2 = n3;
        count = count - 1;
    }


    return 0;
}

Output:
Enter the limit
10

0
1
1
2
3
5
8
13
21
34

Logic to Generate Fibonacci Series in C Programming Language

We know that the first 2 digits in fibonacci series are 0 and 1. So we directly initialize n1 and n2 to 0 and 1 respectively and print that out before getting into while loop logic. Since we’ve already printed two fibonacci numbers we decrement the value of variable count by 2.

Inside while loop
We already know that C program treat any non-zero number as true and zero as false. So once the value of variable count is zero, the execution of while loop stops. So the condition while(count) is equal to writing while(count == 0). We decrement the value of count by 1 each time the loop executes. So once count is 0 the loop execution stops.

As per definition of Fibonacci series: “..each subsequent number is the sum of the previous two.” So we add n1 and n2 and assign the result to n3 and display the value of n3 to the console.

Next, we step forward to get next Fibonacci number in the series, so we step forward by assigning n2 value to n1 and n3 value to n2.

While loop keeps repeating above steps until the count is zero. If the user entered limit/count as 10, then the loop executes 8 times(as we already printed the first two numbers in the fibonacci series, that is, 0 and 1).

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