CS111 Lab 6 Recursion Part II

1. Write a recursive algorithm to multiply two positive integers x and y using repeated addition.
   
   
   
   
2. Write a recursive method that returns the sum of the squares of the first n positive integers.
   Re write using a looping structure.
   
   
   
   
   
3. Zombies standing in a line, numbered 1, 2, ...
   The odd zombies (1, 3, ..) have the normal 2 eyes.
   The even zombies (2, 4, ..) have 3 eyes.
   Write a method zombies() that recursively returns the total number of "eyes" in the zombie line 1, 2, ... n (without loops or multiplication).
   
   
   
   
   
4. Given a non-negative int n, write a method named count() that will return the number of the occurrences of 7 as a digit, so for example 717 yields 2.
   TIP: mod (%) by 10 yields the least significant digit
   (Example: 126 % 10 is 6).
   
   
   
   
   
5. Assume that you have been given an array of integers.
   Write a method array11() that computes recursively the number of times that the value 11 appears in the array.
   TIP: With each recurvise call, consider only the part of the array that begins at a given index.
   For example, a recursive call can pass index+1 to move to the next cell in the array.
   The initial call to the recursive method will pass an index of 0, the first cell in the array.
   
   
   
   
   
6. Assume that you have been given a string containing a sequence of characters.
   Write a method pairStar() that computes recursively a new string where identical chars that are adjacent in the original string are separated from each other by a "*".
   For example, if the original string contains "hello" the final result will be "hel*lo".
   
   
   
7. Given a string, return true if it is a nesting of zero or more pairs of
   parenthesis, like "(())" or "((()))". Suggestion: check the first and last
   characters in a string and then perform recurson on what's inside them.
   
   Examples:
   nestParen("(())") returns true
   nestParen("((()))") returns true
   nestParen("(((x))") returns false
   
   
   Solution:

   
   				public static void main(String[] args) {
   
   					//Program 7
   					String str = "a((xxx(abc)))bb";
   					System.out.println("true: " + nestParen(str));
   					System.out.println("true: " + nestParen("(())"));
   					System.out.println("true: " + nestParen("((()))"));
   					System.out.println("false: " + nestParen("((())"));
   				}
   
   				public static boolean nestParen(String str) {
   					//PRIMITIVE STATES:
   					if (!str.contains("(") && !str.contains(")"))
   					return true;
   					else if (str.length() <= 1)
   					return false;
   					else if (str.length() == 2 && (str.contains(")") || str.contains(")")))
   					return str.charAt(0) == '(' && str.charAt(1) == ')';
   
   					//RECURSIVE MATCH AT THE END
   					if (str.charAt(0) == '(' && str.charAt(str.length() -1) == ')')
   					return true && nestParen(str.substring(1, str.length()-1));
   
   					//REMOVE OUTER NON PARENTHESIS CHARACTERS
   					int s = 0;
   					int e = str.length();
   					if (str.charAt(s) != '(')
   					s++;
   					if (str.charAt(str.length()-1) != ')' && (s < e-1))
   					e--;
   					return nestParen(str.substring(s, e));
   				}