Recursion Practice Problems

Objectives

  • Increase familiarity with recursive logic by working through several recursive problems.

  • Taking into consideration a few corner cases through analyzing the test cases.

  • Using a regex expression that will remove punctuation.

Getting Started

Create a new Java project called L5 and import Recursion-starter.jar. Your eclipse directory should look like this:

L5/
└── src
    └── Recursion.java
Description

Get as many methods done as possible in recitation. Complete the rest of the methods by the following recitation, anything covered in recitation is fair game for exams.

Do not include any for or while loops in your methods. These can all be completed in a purely recursive style.

In the spirit of incremental development, implement each method one at a time, look at the test cases and take into consideration what is being tested, then copy the code into your main method and make sure that your method works.

Warm up

  1. the factorial method

System.out.println("Testing the factorial method");
System.out.printf("factorial(4) should be 24 -> %d\n", factorial(4));
System.out.printf("factorial(6) should be 720 -> %d\n", factorial(6));
System.out.printf("factorial(0) should be 1 -> %d\n", factorial(0));
System.out.println();

  1. the fibonacci method

System.out.println("Testing the fibonacci method");
System.out.printf("fib(0) should be 0 -> %d\n", fib(0));
System.out.printf("fib(1) should be 1 -> %d\n", fib(1));
System.out.printf("fib(2) should be 1 -> %d\n", fib(2));
System.out.printf("fib(5) should be 5 -> %d\n", fib(5));
System.out.printf("fib(10) should be 55 -> %d\n", fib(10));
System.out.printf("fib(13) should be 233 -> %d\n", fib(13));
System.out.println();

Summing a series

  1. the sumDownBy2 method

System.out.println("Testing out the sumDownBy2 method");
System.out.printf("sumDownBy2(-1) should be 0 -> %d\n", sumDownBy2(-1));
System.out.printf("sumDownBy2(0) should be 0 -> %d\n", sumDownBy2(0));
System.out.printf("sumDownBy2(7) should be 16 -> %d\n", sumDownBy2(7));
System.out.printf("sumDownBy2(8) should be 20 -> %d\n", sumDownBy2(8));
System.out.printf("sumDownBy2(13) should be 49 -> %d\n", sumDownBy2(13));
System.out.println();

  1. the harmonicSum method

System.out.println("Testing out the harmonicSum method");
System.out.printf("harmonicSum(0) should be 0.0000 -> %.4f\n", harmonicSum(0));
System.out.printf("harmonicSum(7) should be 2.5929 -> %.4f\n", harmonicSum(7));
System.out.printf("harmonicSum(8) should be 2.7179 -> %.4f\n", harmonicSum(8));
System.out.printf("harmonicSum(13) should be 3.1801 -> %.4f\n", harmonicSum(13));
System.out.printf("harmonicSum(24) should be 3.7760 -> %.4f\n", harmonicSum(24));
System.out.println();

  1. the geometricSum method

System.out.println("Testing out the geometricSum method");
System.out.printf("geometricSum(0) should be 1.0000 -> %.4f\n", geometricSum(0));
System.out.printf("geometricSum(1) should be 1.5000 -> %.4f\n", geometricSum(1));
System.out.printf("geometricSum(2) should be 1.7500 -> %.4f\n", geometricSum(2));
System.out.printf("geometricSum(7) should be 1.9922 -> %.4f\n", geometricSum(7));
System.out.printf("geometricSum(24) should be 2.0000 -> %.4f\n", geometricSum(24));
System.out.println();

More fun with math

  1. the mult method

System.out.println("Testing out the multiplication method");
System.out.printf("mult(8, 2) should be 16 -> %d\n", mult(8, 2));
System.out.printf("mult(2, 8) should be 16 -> %d\n", mult(2, 8));
System.out.printf("mult(4, -3) should be -12 -> %d\n", mult(4, -3));
System.out.printf("mult(-3, 4) should be -12 -> %d\n", mult(-3, 4));
System.out.println();

  1. the expt method

System.out.println("Testing out the exponent method");
System.out.printf("expt(2, 5) should be 32 -> %d\n", expt(2, 5));
System.out.printf("expt(5, 2) should be 25 -> %d\n", expt(5, 2));
System.out.println();

Working with Strings

  1. the isPalindrome method

System.out.println("Testing out the palindrome method");
System.out.printf("isPalindrome(\"a\") should be true -> %b\n", isPalindrome("a"));
// fear of palindromes, lol.
System.out.printf("isPalindrome(\"Aibohphobia\") should be true -> %b\n", isPalindrome("Aibohphobia"));
System.out.printf("isPalindrome(\"noon\") should be true -> %b\n", isPalindrome("noon"));
System.out.printf("isPalindrome(\"Recursion\") should be false -> %b\n", isPalindrome("Recursion"));
System.out.println();

  1. the longestWordLength method

System.out.println("Testing out the longestWordLength method\n");
String quoteOne =
  "Grit, one of the keys to success. The person who perseveres is the one who\n" +
  "will surely win. Success does not come from giving up, it comes from believing\n" +
  "in yourself and continuously working towards the realization of a worthy ideal.\n" +
  "Do not ever give up on what you want most. You know what you truly want.\n" +
  "Believe in your dreams and goals and take daily consistent action in order to\n" +
  "make your dreams a reality.";
System.out.printf("The longest word in the following quote:\n%s\nshould be 12 -> %d\n\n", quoteOne, longestWordLength(quoteOne));
String quoteTwo = "Try to be like the turtle – at ease in your own shell.";
System.out.printf("The longest word in the following quote:\n%s\nshould be 6 -> %d\n\n", quoteTwo, longestWordLength(quoteTwo));
System.out.println();

  1. the dedupeChars method

System.out.println("Testing the dedupeChars method");
System.out.printf("dedupeChars(\"a\") should be a -> %s\n", dedupeChars("a"));
System.out.printf("dedupeChars(\"aa\") should be a -> %s\n", dedupeChars("aa"));
System.out.printf("dedupeChars(\"MiSsisSiPpi\") should be MiSisiPi -> %s\n", dedupeChars("MiSsisSiPpi"));
System.out.printf("dedupeChars(\"swimMmMming\") should be swiming -> %s\n", dedupeChars("swimMmMming"));
Important
 Once you have completed nine or more methods, show your code to the TA or the helper to receive credit.