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.
