---
# System prepended metadata

title: Jam 02 - Exercise 5 - Fibonacci and BigInteger
tags: [BigInteger, recursion, "3 \U0001F9EA in testing", methods, performance, jam02, "4 \U0001F973 done"]

---

---
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.
