---
title: "Jam 02 - Exercise 5 - Fibonacci and BigInteger"
tags:
- 3 š§Ŗ in testing
- 4 š„³ done
- jam02
- methods
- recursion
- performance
- BigInteger
---
<!-- markdownlint-disable line-length single-h1 no-inline-html -->
<!-- markdownlint-configure-file { "ul-indent": { "indent": 4 }, "link-fragments": {"ignore_case": true} } -->
# Exercise 5 - Fibonacci and BigInteger
{%hackmd dJZ5TulxSDKme-3fSY4Lbw %}
{%hackmd dJZ5TulxSDKme-3fSY4Lbw %}
## Overview - Exercise 5
Remember the Fibonacci sequence? Each number is the sum of the two preceding ones (0, 1, 1, 2, 3, 5, 8, 13, ...). While it's a simple concept, implementing it in code reveals fascinating lessons about algorithm design and performance!
In this exercise, you'll:
- Implement the same algorithm in three different ways
- Compare recursive vs non-recursive approaches
- Use BigInteger to handle large numbers
- Measure and analyze performance differences
:::info
š **Need a Refresher?**
Check out the [Fibonacci number Wikipedia page](http://en.wikipedia.org/wiki/Fibonacci_number) to recall how the sequence works. Each number is the sum of the previous two: F(n) = F(n-1) + F(n-2), with F(0) = 0 and F(1) = 1.
:::
## Required Steps - Implementing Fibonacci
1. Create a new file called `Fibonacci.java` in your `jam02` directory. Keep your standard banner comment at the top, then add this code:
```java
package jam02;
import java.math.BigInteger;
import java.util.Scanner;
/**
* A class to demonstrate different approaches to computing Fibonacci numbers,
* comparing recursive, non-recursive, and BigInteger implementations.
*/
public class Fibonacci {
/**
* Compute the nth fibonacci number recursively
*
* @param n - the nth number to find (must be non-negative)
* @return the nth number in the fibonacci sequence
*/
public static int recFib(int n) {
// TODO: Implement the recursive solution using F(n) = F(n-1) + F(n-2)
return 0;
}
/**
* Compute the nth fibonacci number non-recursively, using a while loop.
*
* @param n - the nth number to find (must be non-negative)
* @return the nth number in the fibonacci sequence
*/
public static int nonRecFib(int n) {
// TODO: Implement the non-recursive solution using a while loop
return 0;
}
/**
* Compute the nth fibonacci number non-recursively, using BigInteger
* for unlimited precision.
*
* @param n - the nth number to find (must be non-negative)
* @return the nth number in the fibonacci sequence as a BigInteger
*/
public static BigInteger nonRecFibBigInteger(int n) {
// TODO: Implement the BigInteger solution (similar to nonRecFib)
return BigInteger.ZERO;
}
/**
* Main program to test all fibonacci methods
*/
public static void main(String[] args) {
// Recursive solution becomes very slow above n=40
final int MAX_RECURSIVE_N = 40;
System.out.println("Fibonacci number to compute:");
Scanner scnr = new Scanner(System.in);
int n = scnr.nextInt();
// Store the result from the different ways to compute fib(n)
int recResult = 0;
long startTime, endTime;
if (n <= MAX_RECURSIVE_N) {
startTime = System.nanoTime();
recResult = recFib(n);
endTime = System.nanoTime();
System.out.format("Recursive fib: %,d Time: %.4f ms%n",
recResult, (endTime - startTime) / 1_000_000.0);
} else {
System.out.println("Recursive fib: COULD NOT COMPUTE");
}
startTime = System.nanoTime();
int nonRecResult = nonRecFib(n);
endTime = System.nanoTime();
System.out.format("Non-recursive fib: %,d Time: %.4f ms%n",
nonRecResult, (endTime - startTime) / 1_000_000.0);
startTime = System.nanoTime();
BigInteger nonRecFibBigIntegerResult = nonRecFibBigInteger(n);
endTime = System.nanoTime();
System.out.format("Non-recursive fib with BigInteger: %,d Time: %.4f ms%n",
nonRecFibBigIntegerResult, (endTime - startTime) / 1_000_000.0);
}
}
```
2. Implement these three methods:
```java
public static int recFib(int n) // The recursive version
public static int nonRecFib(int n) // Non-recursive (using while loop)
public static BigInteger nonRecFibBigInteger(int n) // Same as nonRecFib but with BigInteger
```
Complete them in order - each builds on what you learned from the previous one:
- Start with the recursive version (elegant but... you'll see!)
- Then implement it non-recursively with a while loop
- Finally, modify it to use BigInteger for handling large numbers
3. Test each method as you go. The class includes a driver program (a `main` program that tests your methods out). The 40th Fibonacci number is 102,334,155 - all three methods should give you this same result.
> š **Checkpoint**: Before moving on, verify:
>
> - Your `Fibonacci.java` file compiles and runs without errors
> - All three implementations give correct results for n=40
> - Your timing measurements are displayed with 4 decimal places
> - You understand why the recursive version is limited to nā¤40
> - You've documented your findings in `answers.txt` for questions 5.1-5.2
> - Your working directory is clean (no uncommitted changes)
<!-- Comment to split quote boxes -->
>[!Important] Questions for answers.txt
>
>(5.1) Copy your results for computing the 20th, 30th, 40th, and 100th Fibonacci numbers. Include the timing results for all three methods (where possible).
>
>(5.2) Why is the recursive version so much more computationally expensive than the non-recursive version? Think about what's happening behind the scenes with each recursive call.
## Save Your Work - Exercise 5
Verify what files are uncommited:
```bash
git status
```
Stage your changes (This should be the file shown in `git status` as modified)
Feel free to use a different message as long as it's descriptive
```bash
git add src/main/java/jam02/Fibonacci.java src/main/java/jam02/answers.txt
```
Commit your work
```bash
git commit -m "jam02: Complete Fibonacci implementation and analysis"
```
Your working directory should be now be clean.
Sign in with Wallet
Connect another wallet