CSE 214 Computer Science II (Spring 2015)

RECITATION 5 – Recursion

Objective:

  1. To work with Recursion
  2. Analyze the complexity

 

  1. [10 min] Write a recursive function that takes an integer value ‘num’ as a parameter and  prints out the values num to 1 in descending order. 

[link: : http://www3.cs.stonybrook.edu/~sael/teaching/cse214/rec/RevPrint.java]

  1. [10 min] Draw the recursion trace for the execution of reverseArray(data, 0, 4), from given Code Fragment, on array data = 4, 3, 6, 2, 6.

    2. /** Reverses the contents of subarray data[low] through data[high] inclusive. */

    public static void reverseArray(int[ ] data, int low, int high)

    {

    if (low < high)

      { // if at least two elements in subarray

         int temp = data[low]; // swap data[low] and data[high]

         data[low] = data[high];

         data[high] = temp;

         reverseArray(data, low + 1, high − 1); // recur on the rest

       }

    }

  2. [15 min] Write a RECURSIVE function to perform binary sum on an array. The output must be the sum of the n elements present in the array. Also analyze the complexity.

    3. [link: : http://www3.cs.stonybrook.edu/~sael/teaching/cse214/rec/BinarySum.java]

  3. [15 min]  Euclid’s algorithm to find GCD: Given two positive numbers, we can calculate their Greatest Common Divisor by subtracting the larger value by the smaller value, and updating the larger value with the result. Continue until both values are equal, then we have found their GCD. Write a method that determines the GCD of 2 positive numbers. Throw an exception if both values are not positive.

[link: : http://www3.cs.stonybrook.edu/~sael/teaching/cse214/rec/GCD.java]

Practice Question: Describe a recursive algorithmfor computing the nth Harmonic number, defined as Hn = ∑k=1n 1/k