(Textbook. Click for information.)

CS 3343/3341  Analysis of Algorithms  Spring 2012  Recitation 2  Elementary Recursion     Week 2: Jan 24-26  Due (on time): 2012-01-30  23:59:59  Due (late):        2012-02-03  23:59:59

Recitation 2 should be submitted following directions at: submissions with deadlines 2012-01-30  23:59:59 (that's Monday, 30 January 2012, 11:59:59 pm) for full credit. 2012-02-03  23:59:59 (that's Friday, 03 February 2012, 11:59:59 pm) for 75% credit.

1. Study the page Elementary Recursion Examples carefully, paying particular attention to the first part: Number Base Conversion. This part requires no answer.

Lesson: Recursion can give you the use of a stack for free.

2. In the same link as above, examine the excessive execution time taken in calculating Fibonacci numbers using recursion. This part requires no answer.

3. Examine the page Recursive Loops. The Java and C programs each produce exactly the same output. Without executing either program, guess what the output will be. (No peeking.) If you're not brave, then go ahead and execute one or both of the programs. Report your findings as the answer to this part.

Lesson: You can simulate any loop using recursion without a loop. If Java or C had no loop constructs, you could still carry out all the same computations.

4. Write a function harmonic (in Java or C or both) with one parameter n that will calculate and return the sum:

   
   1 + (1/2) + (1/3) + . . . + (1/(n-1)) + (1/n).
   

   Write a second function harmonic2 (in Java or C or both) without using a loop, but using recursion.

   All the calculations should be with doubles. [As a check, the value of harmonic(10) should be 2.9289682539682538.]

5. It turns out that harmonic(n) is approximately equal to ln(n) + γ, where γ = 0.5772156649... is known as Euler's constant. ("ln" is the "natural" log, the log base e.) Use each version of the "harmonic" functions above to check the accuracy of this approximation for n = 1000, 1000000, 1000000000 by printing harmonic(n) - ln(n) for each of those three values. (Depending on your system, you may encounter a problem here.)
   [Note: Let approx(γ) = harmonic(n) - ln(n). Then approx(γ) - γ = O(1/n).]

6. Refer to the page Recursive Selection Sort. This explains how you are to modify one function and write two new ones to produce a recursive selection sort.

Contents of email submission for Recitation 2: Your last name, Your first name; CS 3343; Recitation 2. 3. Answer to the question 3. 4. Code for 2 functions, non-recursive and recursive, each calculating partial sums of the harmonic function. You should show two separate runs, each including the value calculated for harmonic(10). 5. Include a printout of the six values of harmonic(n) - ln(n) for each of the two functions and for each of the three values n = 1000, 1000000, 1000000000. [Or a printout of what happened; in one of the calculations of a billion terms of the series, my computer at home started smoking and blew up.] 6. Include all your souce code for the selection sort, but especially code for the three new functions maxind, selectionsort, exchange. Then give the results of sorting an array of 15 random numbers. (Remember, just a single .txt file, with the parts concatenated together.)

• Getting more familiar with recursion.
• See the five "Lessons" above.
• Working on recursion in a more-complex program.