## Exercise 2: Recursion

Repository

Create all of your answers in a single file called Exercise 2

**Problem 1**

Create the recursive method digitalSum(int n) that given a non-negative int n, return the sum of its digits recursively (no loops). Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6, 12345 % 10 is 5, etc.), while divide (/) by 10 removes the rightmost digit (126 / 10 is 12, 12345 / 10 is 1234, etc. ).

**Sample output:**

digitalSum(126) → 9

digitalSum(49) → 13

digitalSum(12) → 3

**Problem 2**

The digital root of a non-negative integer n is computed as follows. Begin by summing the digits of n. The digits of the resulting number are then summed, and this process is continued until a single-digit number is obtained. For example, the digital root of 2019 is 3 because 2+0+1+9=12 and 1+2=3. Write a recursive function digitalRoot(n) which returns the digital root of n. Make use of the digitalRoot method you wrote in question 1 to help you!

**Sample output:**

digitalRoot(2019) → 3

digitalRoot(126) → 9

digitalRoot(49) → 4

digitalRoot(276) → 6

**Problem 3**

We have triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, and so on. Create a recursive method called triangle(int n) to compute recursively (no loops or multiplication) the total number of blocks in such a triangle with the given number of rows.

**Sample output:**

triangle(0) → 0

triangle(1) → 1

triangle(2) → 3

triangle(3) → 6

**Problem 4**

The Hailstone pattern is generated using 2 simple rules: If the current number, n, in the sequence is even, the next number is n/2, otherwise, the next number is 3*n+1. Repeating this process will generate the Hailstone sequence. Your job is to write a recursive method hailstone(int n) that will print out this sequence for any postive integer n that is greater than 0 until it reaches a value of 1.

**Note:**once your sequence hits 1, you will want to stop the sequence or you will be stuck in an infinite loop.

**Sample output:**

hailstone(5) →

5

16

8

4

2

1

hailstone(12) →

12

6

3

10

5

16

8

4

2

1

**Problem 5**

Create a recursive method called binaryConvert(int n) that will take any positive integer n and will return a String in binary (base 2). To do this, you must first learn how to convert a number in a recursive manner to base 2. We will use repeated division by 2, the quotient and the remainder to do this. The image below will help out the explanation.

To convert the number 156 into binary, we first divide 156 by 2. When we try, we get a quotient of 78 and a remainder of 0. This remainder will be the last digit for our binary conversion. We now take the quotient of 78 and divide it by 2. This gives us a quotient of 39 and a remainder of 0. Again, this 0 is our second last digit. We take the 39 and divide by 2 to get the quotient of 19 and a remainder of 1. This 1 is our third last digit. We continue this patter until we get a quotient of 0, remainder of 1. Now we read all the remainders we got backwards to get our binary conversion of 10011100.

binaryConvert(156) -> 10011100

binaryConvert(13) -> 1101

binaryConvert(1000) -> 1111101000

**Sample Output:**binaryConvert(156) -> 10011100

binaryConvert(13) -> 1101

binaryConvert(1000) -> 1111101000

**Problem 6**

Create a recursive method called convert(int n, int b) that will take any positive integer n and positive base integer b (from 2-16), and convert that integer to the given base and return the answer as a String. If a number converts to a digit that is 10 or bigger, use a letter to replace that digit. So 10->A, 11->B, 12->C, 13->D, 14->E, 15->F. The recursive method is similar to the method from Problem 3, except that the repetitive division by 2 is replace by whatever base they specify. This method works exactly like question 4.

**Sample Output:**

convert(1000,8) -> 1750

convert(1000,16) -> 3E8

convert(1000,2) -> 1111101000

**Problem 7**

A palindrome is a sequence of characters or numbers that looks the same forwards and backwards. For example, "racecar" is a palindrome because it is spelled the same reading it from front to back as from back to front. The number 12321 is a numerical palindrome. Write a function that takes a string and its length as arguments and recursively determines whether the string is a palindrome or not. Name this method isPalindrome(String s, int length) and make it return a boolean instead of just printing it to the screen.

**Sample Output:**

isPalindrome("racecar") -> true

isPalindrome("radar") -> true

isPalindrome("lamont") -> false

**Hint:**the charAt(int n) and substring(int start, int end) commands may come in handy. This is not the only way it could be done though. Look it up in the Java String docs if you would like to learn more about Strings and methods.

## CHALLENGE!

**Problem 8**

This problem came from one of the DWITE competitions. This contest, unfortunately, no longer takes place. You can use a recursive solution similar to Spok's Dilema to solve this problem.

**Jimmy’s Lost His Marbles**

Jimmy Joey Benn keeps losing his marbles, literally, not figuratively. Jimmy keeps his marbles in small bags, but he places these bags all over his house, and keeps forgetting where he places them. To solve his problem, Jimmy has bought a marble storage box where he can put his bags of marbles into. Jimmy wants to store as many marbles as possible in the box, but he wants to keep the marbles in the original bags. Jimmy is particular about his bags of marbles because his bags of marbles are sorted by colour, weight or design. All of Jimmy’s marbles are of the same size. Your job is to help Jimmy place as many marbles, as he can, into his storage box.

For this problem, you are given 2 pieces of information: an integer that contains the maximum amount of marbles that can fit inside the box, and an integer array that contains the number of marbles in each bag of marbles. With this information, determine the maximum number of marbles that can fit inside the box.

**Sample**

**Input:**

50

[12 14 18 33 34 ]

**Output:**

48

**Input:**

100

[12 18 22 67 50 23]

**Output:**

97

**Input:**

75

[25 25 70 50]

**Output:**

75