Fibonacci Number in C using Recursion
Fibonacci Number in C using Recursion Program Description:
Write a C Program to generate the Fibonacci number in C using recursion. The program accepts a number from the user( n) and generates the nth Fibonacci number using the Recursion in C language.
Formula to generate the Fibonacci Number?
The formula to calculate Fibonacci Series is n = (n-1) + (n-2).
F{n} = F{n-1} + F{n-2} so F{0} = 0 and F{1} = 1, etc.
where (n-1) means “the last number before n in the series” and (n-2) refers to “the second last one before n in the series.”
What is Recursion?
A function calling itself is called Recursion. The function called itself is called a recursive function.
We have covered recursion in detail in the Recursion in C Language tutorial.
|
1 2 3 4 5 6 7 8 |
returnType rec_Fun() { .... .... rec_Fun(); // recursive call .... .... } |
Example Input and Output:
Input:
Enter a Number: 10
Output:
10 number Fibonacci number is : 55
Pre-Requisites:
Related Fibonacci Series Programs:
- C Program to generate Fibonacci Series up to a given number
- C Program to Print First n Fibonacci numbers
- C Program to get Nth Fibonacci number
Fibonacci Number in C using Recursion Program Algorithm:
- Get the user input and store it in a variable called num
- If the num is a negative number, display an error message and allow the user to try again.
- Create a function called getFib, The getFib function takes one integer number as input. and returns the generated Fibonacci number.
- Call the getFib function with the input number num. and store the return value in result variable. ( result = getFib(num))
- The
getFib function uses the recursion to generate the Fibonacci number.
- As we already know, The first two Fibonacci numbers are and 1. So our base condition for the recursion is to return num when the num <= 1.
- If the num is not or 1, Then we will make recursive calls to getFib using the getFib(n-1) and getFib(n-2) and add the results. As we can generate the Fibonacci(n) by adding Fibonacci(n-1) and Fibonacci(n-2). F{n} = F{n-1} + F{n-2}
- Once the recursive calls are completed, The getFib function will return an integer value which is the given number or numth Fibonacci number. Finally, Display the result on the console.
Fibonacci Number in C using Recursion Program:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
/* Program to generate Fibonacci number in C using recursion */ #include<stdio.h> /* getFib accepts a number and generates nth fibonacci number. argument_list : int return_type : int */ int getFib(int num) { // if 'num' is '0' or '1' return 'num' // because first two fibonacci numbers are '0' and '1' if(num <= 1) return num; // Otherwise make recursive call to getFib() function // with F(num-1) + F(n-2) return(getFib(num-1) + getFib(num-2)); } int main() { // Take input from the user int num; INPUT: printf("Enter a Number: "); scanf("%d", &num); // Check for the negative number if(num < 0) { printf("Error: Invalid Input, Please enter positive number\n"); goto INPUT; } // call getFib function. // getFib return the nth fib. int result = getFib(num); printf("%d number Fibonacci number is : %d \n", num, result); return 0; } |
Program Output:
Compile and Run the program.
Example 1:
|
1 2 3 4 5 |
$ gcc fib-recursion.c $ ./a.out Enter a Number: 14 14 number Fibonacci number is : 377 $ |
We are getting the expected results. Let’s try few more test cases.
Example 2:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
$ ./a.out Enter a Number: 6 6 number Fibonacci number is : 8 $ ./a.out Enter a Number: 0 0 number Fibonacci number is : 0 $ ./a.out Enter a Number: 2 2 number Fibonacci number is : 1 $ ./a.out Enter a Number: 10 10 number Fibonacci number is : 55 $ |
Example 3: Negative number test case:
|
1 2 3 4 5 6 7 8 |
$ ./a.out Enter a Number: -12 Error: Invalid Input, Please enter positive number Enter a Number: -1 Error: Invalid Input, Please enter positive number Enter a Number: 1 1 number Fibonacci number is : 1 $ |
If the user enters a negative number, the Program display’s error message ( Error: Invalid Input, Please enter positive number). And ask for user input again using the Goto Statement in C language.
Related Program:
- C Program to Check Prime Number using Square Root (Sqrt) Method
- C Program to Print Prime Numbers between Two numbers
- C Program to print First N Prime numbers
- C Program to generate Prime numbers up to N
- C Program to Calculate Nth Prime Number
- C Program Check Prime Number [Mutliple Methods]
- C Program to Convert Decimal Number to Binary Number
- C Program to Convert Binary Number to Decimal Number
- C Program to Convert Octal Number to Decimal Number
