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 $2+9+4+6 = 21$ . 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 ${\bf i}$ 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 ${\bf 2946}$ 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.

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.