Fibonacci Series using Recursion

Fibonacci Series using Recursion 

The Fibonacci series 

0, 1, 1, 2, 3, 5, 8, 13, 21, .. 

Begins with 0 and 1 and has the property that each subsequent Fibonacci number is the sum of the previous two Fibonacci numbers.

The fibonacci series may be defined recursively as follows: 

fibonacci(0) = 0 

fibonacci(1) = 1 

fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)

Recursive Fibonacci function 

#include <stdio. h> 

long Fibonacci (long n); // function prototype 

// function main begins program execution 

int main (void) 

{ 

long result; // fiboncci value 

long number; // number input by user 

// obtain integer from user 

printf(" Enter an integer: "); 

scanf("%d”, &number); // calculate Fibonacci value for number input by user 

result = Fibonacci (number); 

// display result 

printf("Fibonacci (%1d) = %ld\n , number, result); 

return 0; // indicates successful termination 

}  //end main

recursive definition of function Fibonacci 

long Fibonacci (long n) 

{ // base case 

if (n == 0 n == 1) 

{ 

return n; 

} // end if 

else 

{ // recursive step 

return Fibonacci (n -1) + Fibonacci (n - 2); 

} // end else 

} // end function Fibonacci

Output:

Enter an integer: 0 

Fibonacci (0) = 0 

Enter an integer: 1

Fibonacci (1) = 1 

Enter an integer: 2 

Fibonacci (2) = 1 

Enter an integer: 3 

Fibonacci (3) = 2 

Enter an integer: 4 

Fibonacci (4) = 3 

Enter an integer: 5 

Fibonacci (5) = 5 

Enter an integer: 6 

Fibonacci (6) = 8 

Enter an integer: 10 

Fibonacci (10) = 55 

Enter an integer: 20 

Fibonacci (20) = 6765 

Enter an integer: 30 

Fibonacci (30) = 832040 

Enter an integer: 35 

Fibonacci (35) = 9227465

Explanation: 

This program calculates the nth Fibonacci number recursively using function Fibonacci. 

Notice that Fibonacci numbers tend to become large quickly. Therefore, we've chosen the data type lam for the parameter type and the return type in function fibonacci. 

In this program each pair of output lines show a separate run of the program.