Write a java class called **Recursion**. This class should have the following methods:

**public int addDigits(int i)**

This method takes a nonnegative integer parameter and returns the sum of its digits.

For e.g., addDigits(2946) should return 21 which is . This sum needs to be done recursively by calling

**addDigits**method multiple times.**public int findDigitalRoot(int i)**

This method takes a nonnegative integer as a parameter and returns its digital root. The digital root of a number is defined as the single digit number that is left after repeatedly summing the digits of a number. For e.g., the digital root of is 3 and can be found as:

2+9+4+6 = 21

2+1 = 3

Use recursion to find this root.

**public int[][] pascalTriangle(int depth )**

In this method the input parameter is an int called depth and you are required to return a 2D array. The 2D array should contain a**Pascal's Triangle**with depth number of rows.

**Pascal's Triangle:**This triangle has a property that each number is a sum of the two numbers above it except the left and the right edges which are always 1. For e.g.,

**Pascal's Triangle**of depth 4 can be written as:

1

1 1

1 2 1

1 3 1

The circled number in the 4th row and 3rd column, above is equal to the sum of 2 and 1 to the left and right of it in the line above it. Use this property to write a recursive implementation of Pascal's Triangle.

The depth of this Pascal's triangle is 4. Therefore, a call to**pascalTriangle(4)**should return the above triangle in a 2D array like the one shown below. Test your code with multiple depths.

1

1 1

1 2 1

1 3 3 1

**public String toString()**

This method should return a string representation of

**Pascal's Triangle**upto a depth of 7 rows. You are allowed to use a for loop to create a string representation of the 2D array returned from the recursive method.

**Submitting Your Assignment**

Submit your Recursion.java using checking program as PA5.

Note that your code should compile on the department Linux machines, and make sure that you
are submitting the source code rather than the Java class file.