---
title: "Jam 02 - Exercise 4 - Understanding Methods and Recursion"
tags:
- 3 🧪 in testing
- 4 🥳 done
- jam02
- methods
- recursion
- performance
---
<!-- markdownlint-disable line-length single-h1 no-inline-html -->
<!-- markdownlint-configure-file { "ul-indent": { "indent": 4 }, "link-fragments": {"ignore_case": true} } -->

# Exercise 4 - Understanding Methods and Recursion

{%hackmd dJZ5TulxSDKme-3fSY4Lbw %}

Before we dive into our final exercise, let's explore two important Java concepts that build on what we've learned so far.

## Writing Methods in Java

:::info
📚 **Note on Methods (Optional Reading)**
We'll cover methods in detail in zyBooks next week, but if you're curious for a preview, check out Oracle's tutorial on [writing methods](http://docs.oracle.com/javase/tutorial/java/javaOO/methods.html).
:::

In our last exercise, we created an instantiable class – a class that could be used to create objects with data (the last roll value) and behavior (the ability to roll itself). However, we don't always need or want instantiable classes. Sometimes, we just want *class* methods – methods that aren't associated with any particular *instance* of a class. The keyword that determines whether a member is an *instance* or *class* member is **static**.

Let's look at a simple example - a class method to compute the sum of three numbers:

public static int sum(int a, int b, int c) {
    return a + b + c;
}

Let's break down the important parts of the method declaration (in order of appearance):

- `public` – determines the scope of the method (more on this later)
- `static` – makes this a class method, not an instance method
- `int` – the return type (what kind of value this method gives back)
- `sum` – the method name (follows Java identifier rules)
- *Parameters* – input values in parentheses, each with its type
- *Braces* – contain the method's statements
- `return value` – specifies what to give back when done (must match the declared return type)

To call this method from a main program in the same class:

int result = sum(10, 20, 30);  // stores 60 in result

:::info
🔑 **Note**: Have you noticed that the `main` method in your classes is also a *class* method? That's why it's marked `static` - it's never associated with any instance of the class.
:::

## Recursion in Java

You've likely encountered recursion before - it's a powerful technique where problems are defined in terms of smaller versions of themselves. Once you have a method defined, you can call that method on a smaller instance of the problem.

Let's see this in action with factorial calculations. Create a new file called `Factorial.java` in your `jam02` directory. Keep your standard banner comment at the top, then add this code:

package jam02;

import java.math.BigInteger;
import java.util.Scanner;

/**
 * A class to demonstrate recursion and BigInteger using factorial calculations
 */
public class Factorial {
    /**
     * Recursive function to compute the factorial of a number
     *
     * @param num - number to compute
     * @return the factorial of num
     */
    public static long fac(long num) {
        if (num == 0) {                 // Our base case: num = 0
            return 1;
        }
        return num * fac(num - 1);      // Our recursive call
    }

    /**
     * Recursive function to compute the factorial of a number with BigInteger
     * 
     * @param num - number to compute
     * @return the factorial of num as a BigInteger
     */
    public static BigInteger facBigInteger(BigInteger num) {
        if (num.equals(BigInteger.ZERO)) {
            return BigInteger.ONE;
        }
        return num.multiply(facBigInteger(num.subtract(BigInteger.ONE)));
    }

    public static void main(String[] args) {
        System.out.print("Please enter a number: ");
        Scanner in = new Scanner(System.in);
        long num = in.nextLong();

        // Compute results with a primitive long and with BigInteger
        long answer = fac(num);
        BigInteger bigIntAnswer = facBigInteger(BigInteger.valueOf(num));

        // Report results
        System.out.format("fac(%d) = %d%n", num, answer);
        System.out.format("facBigInteger(%d) = %s%n", num, bigIntAnswer);
    }
}

Take a moment to explore the code, particularly how the recursive methods work. Then run the program and try it with some small numbers first (like 5 or 10) to see the recursion in action. Try tracing through how fac(3) would work on paper.

Then try larger numbers like 30. You should see something interesting:

Please enter a number: 30
fac(30) = -8764578968847253504
facBigInteger(30) = 265252859812191058636308480000000

Wait... that first result can't be right! The problem? **Primitive types have a limited number of bits**. The `long` type uses 64 bits, and if your value needs more than that, you get garbage results like we see above.

## Working with BigInteger

Java provides `BigInteger` and `BigDecimal` in the `java.math` package for when you need to work with really big numbers - numbers so big they won't fit in regular numeric types! However, since these numbers can grow beyond Java's normal numeric limits, you can't use regular math operators like `+` or `*` with them. Instead, you'll need to use their built-in methods like `add()` and `multiply()` to do calculations.

Let's look at some `BigInteger` examples:

// Creating BigIntegers
BigInteger bigIntA = new BigInteger("123");
// or
bigIntA = BigInteger.valueOf(123);  // only for long or smaller

// Subtracting 1
bigIntA = bigIntA.subtract(BigInteger.ONE);  // ONE is a constant

// Multiplying two BigIntegers
BigInteger bigIntB = new BigInteger("456");
BigInteger bigIntC = bigIntA.multiply(bigIntB);
System.out.println(bigIntC);  // prints: 56088

Look at how the factorial method changes when using `BigInteger`:

// Regular factorial
public static long fac(long num) {
    if (num == 0)
        return 1;
    return num * fac(num - 1);
}

// BigInteger factorial
public static BigInteger facBigInteger(BigInteger num) {
    if (num.equals(BigInteger.ZERO))
        return BigInteger.ONE;
    return num.multiply(facBigInteger(num.subtract(BigInteger.ONE)));
}

The methods are functionally identical, but notice how every operation must use `BigInteger` methods instead of regular operators.

Now when you run the program with large numbers, `facBigInteger` gives correct results:

Please enter a number: 30
fac(30) = -8764578968847253504
facBigInteger(30) = 265252859812191058636308480000000

>[!Important] Questions for answers.txt
>
>(4.1) What is the largest factorial you can compute correctly with the regular `fac` method before it gives incorrect results? How can you tell the result is incorrect?

<!-- Comment to split quote boxes -->

> 🔍 **Checkpoint**: Before moving on, verify:
>
> - Your `Factorial.java` file compiles and runs without errors
> - You can explain why the regular factorial gives incorrect results for large numbers
> - You understand how BigInteger helps with large number calculations
> - You've documented your findings in `answers.txt` for question 4.1
> - Your working directory is clean (no uncommitted changes)

## Save Your Work - Exercise 4

Verify what files are uncommited:

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

git add src/main/java/jam02/Factorial.java src/main/java/jam02/answers.txt

Commit your work

git commit -m "jam02: Complete methods and recursion exploration"

Your working directory should be now be clean.