• Home
• Contact Me
•
Aeries Portal
• Royal High School
• Simi Valley USD

AP Statistics

• Course Calendar
• Chapter Notes
• Practice Tests

AP Comp-Sci
Course Content
• Programs
• Practice Tests

CP Statistics
• Course Calendar
• Chapter Notes
• Practice Tests

Algebra
Geometry

Math Power

AP Computer Science Unit 5 Programs
Manipulating Data: Sorting, Searching and Recursion

WORKING WITH RECURSIVE ALGORITHMS

 (1)  The exclamation point symbol (!) is used in mathematics and is given the name factorial. It is defined as follows: n! = n*(n-1)*(n-2) … 3*2*1. For example, 5! = 5*4*3*2*1=120. Write a recursive method that will compute and return the factorial of any integer. (2)  Recall the algorithm for find the greatest common divisor (GCD) of two integers x and y: Let r = x % y If r=0, then GCD = y If r!=0, then do the following: Let x=y Let y=r Got back to step 1 You originally did this problem when we studied loops. Now write a program that uses a recursive method to find the GCD of two integers input by the user. Display the GCD when it is found. Try a variety of values to test your program. (3)  Let’s now take a look at another recursive method to further analyze the stacking concept. Below is the method whatsTheOutput: public static void whatsTheOutput() // accepts a char input,terminates when a period is entered {      EasyReader keybd = new EasyReader();      char letter;      letter = keybd.readChar();      if (letter != ‘.’)          whatsTheOutput( );      System.out.print(letter); } a. Assume that the input sequence of letters is H-E-L-L-O-.. What will the output be? b. Now try it on the computer and see what the true results are. Explain what is happening and compare it to what you thought would happen. (4)  Recall that the digital root of an integer is the sum of its digits. If that sum is not a single digit number, you repeat the process with the sum until you do have a single digit. For example, the digital root of 4726 is 4+7+2+6 = 19 = 1+9 = 10 = 1+0 = 1.The iterative version might be written as follows: public static int dr(int num) {      int temp;      while (num>9)      {          temp = 0;          while (num!=0)          {               temp+=num % 10;               num = num / 10; // or num /= 10;          }          num = temp;      }      return(num); } Now write a recursive version of function dr on the computer. Test it with the example data given above. NOTE: This is a challenging problem! (5)  Pascal’s Triangle is a famous arrangement of numbers first discovered by the Chinese. The name Pascal, however, comes from the French mathematician/philosopher Blaise Pascal, who did extensive work with this triangle and found that it had many connections to various branches of mathematics, such as probability. Recall that the triangle appears as follows: 1 1 1 1 2 1 1 3 3 1 etc… In which each of the numbers in the triangle is the sum of the 2 numbers above it. An alternative arrangement of the triangle is as follows: 1 1 1 1 2 1 1 3 3 1 etc…   The numbers in the triangle can be generated using the following recursive algorithm: For row n and column k, the coefficients of Pascal’s Triangle, C(n, k), can be found by C(n, 0) = 1 C(n, k) = 0, if k > n C(n, k) = C(n-1, k) + C(n-1, k-1), for n ≥ k > 0 Important Note: The first row is defined as row 0 and the first column is defined as column 0. Your first job is to write a recursive function that will generate the coefficient for any given row and column location. For example, a call of C(2, 1) will return 2, since the coefficient at row 2, column 1 is 2. The second task is to use this function, along with nested loops, to generate and display rows 0 through 9 of Pascal’s Triangle in the format as shown in the alternative arrangement above. Don’t worry if things don’t look quite so “pretty.”