# CS161 Assignment 5: Recursion

The objective of this assignment is to practice recursion. You are not supposed to use loops while writing this program.

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

• Note: You are allowed to use a for loop as long as each element is computed recursively.

• 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.