Introduction to the Design and Analysis of Algorithms
(Textbook. Click for information.)
 CS 3343/3341
 Analysis of Algorithms
 Spring 2012
 Recitation 2
 Elementary Recursion

    Partial Answers  

  1. Study the page Elementary Recursion Examples carefully.

  1. 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. The first two functions print in straightforward order: from 10 down to 0, while the third one prints from 0 up to 10, the reverse order.

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

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

    Here's everything in one program:

    // Harmonic.java: harmonic function
public class Harmonic {
  


   static double harmonic0(int n) {
      double res = 0.0;
      while (n > 0) {
         res += 1.0/n;
         n = n - 1;
      }
      return res;
   }

   static double harmonic(int n) {
      if (n == 1) return 1;
      return 1.0/n + harmonic(n - 1);
   }

   public static void main(String[] args) {
      int n = 1000000000;
      double res;
      System.out.println("harmonic0:\n");
      res = harmonic0(n);
      System.out.println(res);
      System.out.println("harmonic:\n");
      res = harmonic0(n);
      System.out.println(res);
      System.out.println(res - Math.log(n));
   }
}
    // harmonic.c: harmonic function
#include 
#include 
#define N 1000000000

double harmonic0(int n) {
   double res = 0.0;
   while (n > 0) {
      res += 1.0/n;
      n = n - 1;
   }
   return res;
}

double harmonic(int n) {
   if (n == 1) return 1;
   return 1.0/n + harmonic(n - 1);
}

void main() {
   double res;
   // printf("harmonic0:\n");
   // res = harmonic0(10);
   // printf("%20.16f\n", res);
   printf("harmonic:\n");
   res = harmonic0(N);
   printf("%20.16f\n", res);
   printf("%20.16f\n", res - log(N));
}
    [with n = 1000000000 above, got, after 18 secs]
harmonic0:  21.30048150234615 [another 18 secs]
harmonic:   21.30048150234615
0.57721 56653 99737 8 [Correct to 10 places.
True value, Euler's Const:
0.57721 56649 01532 86060 65120]

    [with N = 1000000000, got after 20 seconds]
 21.3004815023434091
0.57721 56653 96998 6
[recursive part ran for N = 100000,
gave segmentation fault with N = 1000000]

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

  2. 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).] [All the above questions are answered by the program above and its output. The recursive version worked in Java, with N = 1000000000, which must mean that the tail recursion was turned into a loop. The C version wouldn't work at N = 1000000.]

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

Revision date: 2012-02-06. (Please use ISO 8601, the International Standard.)