The Fibonacci sequence (denoted by f0, f1, f2 …) is as follows:
Fibonacci sequence
2
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …
That is, f0 = 0 and f1 = 1 and each succeeding term is the sum of the two preceding terms. For example, the next two terms of the sequence are
34 + 55 = 89 and 55 + 89 = 144
Many algorithms have both iterative and recursive formulations. Typically, recursion is more elegant and requires fewer variables to make the same calculations. Recursion takes care of its book-keeping by stacking arguments and variables for each method call. This stacking of arguments, while invisible to the user, is still costly in time and space.
Fibonacci sequence is recursively defined by
f0 = 0, f1 = 1, fi+1 = fi + fi-1 for i = 1, 2 …
Fibonacci class is implemented in Program 2, with iterative and recursive methods, and tested by main() driver.
Program 2: Fibonacci sequence
-------------------------------------------------------------
import java.io.*;
class Fibonacci {
public int fibonacciSeq(int n) // Iterative method
{
int term1 = 0, term2 = 1, nextTerm = 0;
if( n == 0 || n == 1) return n;
int count = 2;
while( count <= n )
{
nextTerm = term1 + term2;
term1 = term2;
term2 = nextTerm;
count++;
}
return nextTerm;
}
public int recFibonacciSeq(int n) // Recursive method
{
if( n == 0 || n == 1) return n;
else
return( recFibonacciSeq(n-1) + recFibonacciSeq(n-2) );
}
}
/////////////////// FibonacciDemo.java ////////////////////////
class FibonacciDemo
{
public static void main(String[] args) throws IOException
{
Fibonacci fib = new Fibonacci();
BufferedReader kb = new
BufferedReader(new InputStreamReader(System.in));
// nth value in the Fibonacci sequence
System.out.print("Enter n: ");
int n = Integer.parseInt(kb.readLine());
System.out.println("Iterative method: Fibonacci number "
+ n + " is " + fib.fibonacciSeq(n) );
System.out.println("Recursive method: Fibonacci number "
+ n + " is " + fib.recFibonacciSeq(n) );
}
-----------------------------------------------------------
Output of this program is:
Enter n: 12
Iterative method: Fibonacci number 12 is 144
Recursive method:
This website was created for free with Own-Free-Website.com. Would you also like to have your own website?
