Lab: 22 - Recursion

Assigned

Friday, 13 October 2023

Summary

This lab will give you practice with recursive methods in Java.

(1/2 point) Start this lab session by sharing something (a new Java method or eclipse shortcut) you learned this week.
Add the answers to your lab report—at least two ideas per student. 

The following link will demonstrate -using a visualization- the implementation of a Recursive Factorial algorithm Recursive Factorial.

While designing your solution you might want to consider the following questions:

• Is the recursive method static or non-static?
• What is the base case for the recursive method?
• What is the recursive case?

Convert Decimal to another number base

(1 1/2 points) Write a method that convert a decimal number to any other base. For example:

100 >> 1100100 (base 2 - binary)
100 >> 144 (base 8 - octal)
100 >> 64 (base 16 - hexadecimal) 

To design your solution you might want to consider the following:

• Start simple, write a solution considering converting only up to base = 10.
• Then update your solution to work up to base 16 (hexadecimal).
• Your main method should ask the user the decimal number and the base (a number).

Your method should throw an IllegalArgumentException with a customized message for invalid values.

Fibonacci Sequence

(2 points) The Fibonacci sequence is a series of numbers in which each number is the sum of the previous two numbers. For example, the first 10 numbers of the sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ....

The series can be calculated using either iteration or recursion to find the number in the nth position of the sequence. For this lab, use a recursive approach.

To design your solution you might want to consider the following:

• Your recursive method will not print the sequence. It should only calculate the Fibonacci number at position received as parameter.
• The series starts at position 0 (position 0 = 0, position 1 = 1, position 2 = 1, position 3 = 2).
• Your main method should ask the user how many Fibonacci numbers to print. Then, use a loop to calculate and then print each Fibonacci number up to the requested.

The following is a correct but inefficient approach to compute the nth Fibonacci number:

	public static int fibonacci(int n) {
		if (n<=2)
			return 1;
		return fibonacci(n-1) + fibonacci(n-2);
	}

The code shown runs slowly. How many times is the method called for n = 8, n = 9, n= 10?

Write a new version of this method that is still recursive and has the same header but is more efficient. Do this by creating a helper method that accepts additional parameters, such as previous Fibonacci numbers that you can carry through and modify during the recursive call.

How many times is the new method called for n = 8, n = 9, n= 10?

Your method should throw an IllegalArgumentException with a customized message for invalid values.

Writing Sequences

(2 points) Write a method called writeSequence that accepts an integer n as a parameter and prints to the console a symmetric sequence of n numbers composed of descending integers that ends in 1, followed by a sequence of ascending integers that begin with 1. The following table indicates the output that should be produced for various values of n:

Your method should throw an IllegalArgumentException with a customized message if it is passed a value less than 1.

Lab Submission

You will submit your source files and lab report (include the output of each program) via Gradescope by the end of the week.

I strongly recommend that each student keep a copy of the lab. Therefore, don’t forget to share the files/folder with your lab partner!

Remember: Do not use magic numbers, write your code anticipating errors and print user-friendly error messages, all your public methods should be well documented (use Javadoc comments). Please include comments or organize your code and report in a way that will help the grader to find the answer to the exercises or posted questions.

Acknowledgements

From Data Structures & Problem Solving Using Java by Mark Allen Weiss