1. (Recursive strategys efficiency). The maximum number represented by int data type is 2,147,483,647. The value of Fibonacci (n) grows exponentially as we mentioned in the class.

a. Run your program to calculate Fibonacci(n) sequence to find the minimum n which makes that the value of Fibonacci (n) exceeds the maximum value of the signed 32-bit integer.

b. The recursive algorithm for Fibonacci (n) is so inefficient that it takes unreasonable time to run it when n is larger enough, i.e., every time n goes up by 1, the computational time almost doubles. To verify recursive strategys inefficiency in this case, run your program and compare the runtime to calculate Fibonacci value using iterative strategy and recursive one, what is the difference of the runtime?

c. If the value of Fibonacci (n) exceeds the maximum integer your computer can hold, you can use BigInteger class in Java. Run the following codes to find the value of Fibonacci which just exceeds 2,147,483,647.

package HW2; import java.math.BigInteger;

public class FibonacciBigInt {

public static void main( String[] args ) {

int n=47;

BigInteger f1=new BigInteger("1");

BigInteger f2=new BigInteger("1");

BigInteger f=new BigInteger("1");

for(int i=3;i<=n;i++) {

f=f2.add(f1);

f2=f1;

f1=f;

}

System.out.println("The +n+th Fibonacci term is: "+f);

}

}