# 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.

### Example Input and Output:

Input:

Enter a Number: 10

Output:

10 number Fibonacci number is : 55

## Fibonacci Number in C using Recursion Program Algorithm:

1. Get the user input and store it in a variable called num
2. If the num is a negative number, display an error message and allow the user to try again.
3. Create a function called getFib, The getFib function takes one integer number as input. and returns the generated Fibonacci number.
4. Call the getFib function with the input number num. and store the return value in result variable. ( result = getFib(num))
5. 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}&nbsp;=&nbsp;F{n-1}&nbsp;+&nbsp;F{n-2}
6. 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:

### Program Output:

Compile and Run the program.

Example 1:

We are getting the expected results. Let’s try few more test cases.

Example 2:

Example 3: Negative number test case:

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:

1. C Program to Check Prime Number using Square Root (Sqrt) Method
2. C Program to Print Prime Numbers between Two numbers
3. C Program to print First N Prime numbers
4. C Program to generate Prime numbers up to N
5. C Program to Calculate Nth Prime Number
6. C Program Check Prime Number [Mutliple Methods]
7. C Program to Convert Decimal Number to Binary Number
8. C Program to Convert Binary Number to Decimal Number
9. C Program to Convert Octal Number to Decimal Number Venkatesh

Hi Guys, I am Venkatesh. I am a programmer and an Open Source enthusiast. I write about programming and technology on this blog.