10. Recursion

Feel free to use your laptop
You are strongly encourage to work with others
- When you get stuck, ask those sitting around you for help
- Get used to working together in the labs
- Peer teaching and peer learning has been empirically shown to be very effective

10.1. Recursion Visualization

Check out the following website to help visualize recursion:
- https://cscircles.cemc.uwaterloo.ca/java_visualize/

Try running the following in the visualizer

public class Recursion {
    public static void main(String[] args) {
        sum(5);
    }

    public static int sum(int n) {
        if (n == 1) {
            return 1;
        }
        return n + sum(n - 1);
    }
}

10.2. Factorial

Note

Obviously one can simply copy the code from the Recursion Topic, but this defeats the purpose of the lab. Instead, slowly and deliberately implement each method and take the time to understand the details.

Read up on factorial
Write an iterative method to return the factorial of n
- This method will take n as a parameter
- The method will return the factorial
Write a recursive method to return the factorial of n
- This method will take n as a parameter
- This recursive method must start at n and work down to 1
- The method will return the factorial
Write a recursive method to return the factorial of n
- This method will take n and current as a parameter
- This recursive method must start at current (which will start at 1) and work up to n
- The method will return the factorial

10.3. Linear Search on an Array

Write a recursive method to do a linear search
- This method will take an array of integers haystack, an integer needle, and the current index current as parameters
- This method will return a boolean indicating if the needle was found

10.4. Building a Linked Structure

Write a recursive method to build a linked structure containing the numbers 0 – (n-1)
- This method will take an integer n and any other required parameters
- This method will return a reference to the head of the linked structure
- The first node must contain 0
- This will require a working Node class

10.5. Linear Search on a Linked Structure

Write a recursive method that performs a linear search on a linked structure
- The method will take a reference to the current node called current and the needle
- This method will return a boolean indicating if the needle was found