CSC300: Recursion Mistakes

Contents [0/14]

Starter code [1/14]
Does this work? [2/14]
Does this work? [3/14]
Does this work? [4/14]
Does this work? [5/14]
Does this work? [6/14]
Does this work? [7/14]
Does this work? [8/14]
Does this work? [9/14]
Does this work? [10/14]
Does this work? [11/14]
Does this work? [12/14]
Does this work? [13/14]
Python performance [14/14]

(Click here for one slide per page)


Starter code [1/14]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
package algs11;
import java.util.Arrays;
import stdlib.*;
public class Playground {
  /* Return number of times 5.0 occurs in the list */
  public static int numFives (double[] list) {
    return StdRandom.uniform (100); //TODO: fix this
  }
  /* This is a test function */
  public static void testNumFives (int expected, double[] list) {
    int actual = numFives (list);
    if (expected != actual) {
      StdOut.format ("Failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, Arrays.toString (list));
    }
  }
  /* A main function for testing */
  public static void main (String[] args) {
    testNumFives (0, new double[] { });
    testNumFives (1, new double[] { 5 });
    testNumFives (0, new double[] { 11 });
    testNumFives (3, new double[] { 5, 5, 5 });
    testNumFives (0, new double[] { 11, 21, 31, 41 });
    testNumFives (1, new double[] { 5, 11, 21, 31, 41 });
    testNumFives (1, new double[] { 11, 21, 31, 41, 5 });
    testNumFives (1, new double[] { 11, 21, 5, 31, 41 });
    testNumFives (3, new double[] { 11, 21, 5, 31, 5, 41, 5});
    StdOut.println ("Finished tests");
  }
  /* A main function for debugging -- change the name to "main" to run it */
  public static void main2 (String[] args) {
    //Trace.drawSteps ();
    Trace.drawStepsOfMethod ("numFives");
    Trace.drawStepsOfMethod ("numFivesHelper");
    Trace.run ();
    double[] list = new double[] { 5, 11, 5, 5 };
    double result = numFives (list);
    StdOut.println ("result: " + result);
  }
}

Does this work? [2/14]

01
02
03
04
05
06
07
08
09
10
11
 
  public static int numFives (double[] a) {
    return numFives (a, 0, 0);
  }
  private static int numFives (double[] a, int i, int result) {
    if (i>=a.length) 
      return result;
    if (a[i] == 5.0) 
      return numFives (a, i+1, result+1);
    else
      return numFives (a, i+1, result);
  }

Does this work? [3/14]

01
02
03
04
05
06
07
08
09
10
11
 
  public static int numFives (double[] a) {
    return numFives (a, 0, 0);
  }
  private static int numFives (double[] a, int i, int result) {
    if (i>=a.length) 
      return result;
    if (a[i] == 5.0) 
      numFives (a, i+1, result+1);
    else
      numFives (a, i+1, result);
  }

Does this work? [4/14]

01
02
03
04
05
06
07
08
09
10
11
 
  public static int numFives (double[] a) {
    return numFives (a, 0, 0);
  }
  private static int numFives (double[] a, int i, int result) {
    if (i>=a.length) 
      return 0;
    if (a[i] == 5.0) 
      return numFives (a, i+1, result+1);
    else
      return numFives (a, i+1, result);
  }

Does this work? [5/14]

01
02
03
04
05
06
07
08
09
10
11
 
  public static int numFives (double[] a) {
    return numFives (a, 0, 0);
  }
  private static int numFives (double[] a, int i, int result) {
    if (i>=a.length) 
      return result;
    if (a[i] == 5.0) 
      return numFives (a, i++, result+1);
    else
      return numFives (a, i++, result);
  }

Does this work? [6/14]

01
02
03
04
05
06
07
08
09
10
11
 
  public static int numFives (double[] a) {
    return numFives (0, 0);
  }
  private static int numFives (int i, int result) {
    if (i>=a.length) 
      return result;
    if (a[i] == 5.0) 
      return numFives (i+1, result+1);
    else
      return numFives (i+1, result);
  }

Does this work? [7/14]

01
02
03
04
05
06
07
08
09
10
11
12
13
 
  private static double[] b;
  public static int numFives (double[] a) {
    b=a;
    return numFives (0, 0);
  }
  private static int numFives (int i, int result) {
    if (i>=b.length) 
      return result;
    if (b[i] == 5.0) 
      return numFives (i+1, result+1);
    else
      return numFives (i+1, result);
  }

Does this work? [8/14]

01
02
03
04
05
06
07
08
09
10
11
 
  public static int numFives (double[] a) {
    return numFives (a, 0, 0);
  }
  private static int numFives (double[] a, int i, int result) {
    if (i>=a.length) 
      return result;
    if (a[i] == 5.0) 
      return 1 + numFives (a, i+1, result);
    else
      return numFives (a, i+1, result);
  }

Does this work? [9/14]

01
02
03
04
05
06
07
08
09
10
11
 
  public static int numFives (double[] a) {
    return numFives (a, 0);
  }
  private static int numFives (double[] a, int i) {
    if (i>=a.length) 
      return 0;
    if (a[i] == 5.0) 
      return 1 + numFives (a, i+1);
    else
      return numFives (a, i+1);
  }

Does this work? [10/14]

01
02
03
04
05
06
07
08
09
10
11
 
  public static int numFives (double[] a) {
    return numFives (a, 0, 0);
  }
  private static int numFives (double[] a, int i, int result) {
    if (i>=a.length) 
      return result;
    if (a[i] == 5.0) 
      result = result+1;
    result = numFives (a, i+1, result);
    return result;
  }

Does this work? [11/14]

01
02
03
04
05
06
07
08
09
10
11
 
  public static int numFives (double[] a) {
    return numFives (a, 0);
  }
  private static int numFives (double[] a, int i) {
    if (i>=a.length) 
      return 0;
    int result = numFives (a, i+1);
    if (a[i] == 5.0) 
      result = result+1;
    return result;
  }

Does this work? [12/14]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
 
  public static int numFives (double[] a) {
    return numFives(a, 0, 0);
  }
  private static int numFives (double[] a, int i, int result) {
    if (a.length == 0) {  
      return 0;
    }
    if (a.length < 2) {
      if (a[0] == 5) result++;
      return result;
    }
    if (i < a.length) {
      if (a[0] == 5) result++;
      return numFives(a, i+1, result);
    } else {
      return result;
    }   
  }

Does this work? [13/14]

01
02
03
04
05
06
07
08
 
  public static int numFives (double[] a) {
    if (a.length == 0) 
      return 0;
    int result = numFives (Arrays.copyOfRange (a, 1, a.length));
    if (a[0] == 5.0)
      result += 1;
    return result;  
  }

This corresponds to the following code in python:

01
02
03
04
05
06
07
 
def numFives (a):
  if len(a) == 0: 
    return 0
  result = numFives (a[1:])
  if (a[0] == 5.0):
    result += 1
  return result

Python performance [14/14]

file:XnumFivesRecursive.py [source]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
def numFives1 (a, i=0):
  if len(a) == i: 
    return 0
  result = numFives1 (a, i+1)
  if (a[i] == 5.0):
    result += 1
  return result

def numFives2 (a):
  if len(a) == 0: 
    return 0
  result = numFives2 (a[1:])
  if (a[0] == 5.0):
    result += 1
  return result

import time
import sys
sys.setrecursionlimit(10**6)
for f in [numFives1, numFives2]:
  print ("testing " + f.__name__)
  assert 0 == (f ([ ]))
  assert 1 == (f ([ 5 ]))
  assert 0 == (f ([ 11 ]))
  assert 3 == (f ([ 5, 5, 5 ]))
  assert 0 == (f ([ 11, 21, 31, 41 ]))
  assert 1 == (f ([ 5, 11, 21, 31, 41 ]))
  assert 1 == (f ([ 11, 21, 31, 41, 5 ]))
  assert 1 == (f ([ 11, 21, 5, 31, 41 ]))
  assert 3 == (f ([ 11, 21, 5, 31, 5, 41, 5]))
  base = 2000
  for multiplier in [1, 2, 4, 8]:
    length = base * multiplier
    lst = [i for i in range(length)]        
    start = time.time()
    result = f (lst)
    end = time.time()
    print ("Duration of " + f.__name__ + "(" + str(len(lst)) + "): " + str(end - start))

print ("Finished tests")

Revised: 2008/03/17 13:01