CSC300: Lecture 2 (Induction, Iteration and Recursion)

Contents [0/32]

Homework [1/32]
Objects: What is memory? [2/32]
Objects: Base types [3/32]
Objects: Objects and equality [4/32]
Recursion, Briefly: Recursion and collections [5/32]
Recursion, Briefly: Reading pure recursive functions [6/32]
Recursion, Briefly: Reading pure recursive functions [7/32]
Induction: Is this function useful? [8/32]
Induction: Is this function useful? [9/32]
Induction: Is this function useful? [10/32]
Induction: Is this function useful? [11/32]
Induction: Is this function useful? [12/32]
Code variations: Testing [13/32]
Code variations: While loop version [14/32]
Code variations: Recursive version (forward) [15/32]
Code variations: Recursive version (backward) [16/32]
Code variations: Backwards and forwards [17/32]
Common mistakes: Starter code [18/32]
Common mistakes: Does this work? [19/32]
Common mistakes: Does this work? [20/32]
Common mistakes: Does this work? [21/32]
Common mistakes: Does this work? [22/32]
Common mistakes: Does this work? [23/32]
Common mistakes: Does this work? [24/32]
Common mistakes: Does this work? [25/32]
Common mistakes: Does this work? [26/32]
Common mistakes: Does this work? [27/32]
Common mistakes: Does this work? [28/32]
Common mistakes: Does this work? [29/32]
Common mistakes: Does this work? [30/32]
Common mistakes: Does this work? [31/32]
Common mistakes: Does this work? [32/32]

Homework [1/32]

Objects: What is memory? [2/32]

What does the machine memory look like when you see a picture like this:

memory-layout-numFives

To fully answer this question, you need to take the systems classes. But it is useful to have an idea of the memory, even if the details are not exactly correct.

Method calls (Stack) Objects (Heap)
Address Value Description
0xbeef0098??@1.overhead
0xbeef00900xface0000@1.args
0xbeef00880xface0010@1.list

0xbeef0080??@2.overhead
0xbeef00780xface0010@2.a
0xbeef00703@2.i
0xbeef00682@2.result
Address Value Description
0xface00385.0Array.data[3]
0xface00305.0Array.data[2]
0xface002811.0Array.data[1]
0xface00205.0Array.data[0]
0xface00184Array.length
0xface0010??Array.overhead

0xface00080Array.length
0xface0000??Array.overhead

Above, I show two parts of memory. On the left is storage for method calls (commonly called the stack), on the right is storage for objects (commonly called the heap). Arrays are objects in java. Machine addresses are shown as hexadecimal [Search] numbers beginning with the prefix 0x.

Each entry includes some overhead.

Objects: Base types [3/32]

PythonJava
01
02
03
04
i = 0
while (i < 3):
  print ("Hello")
  i = i + 1
01
02
03
04
05
06
07
08
09
10
11
package algs11;
import stdlib.*;
public class Hello {
  public static void main (String[] args) {
    int i = 0;
    while (i < 3) {
      StdOut.print ("Hello");
      i = i + 1;
    }
  }
}

In python, everything is an object. This makes the language quite simple, but comes at a cost.

If you change int to Integer in the program above, then it will run like a python program.

Integer is an object type, whereas int is a base types.

Base values can be directly manipulated by the arithmetic hardware of the computer, whereas object values cannot.

If we use Integer, there will be many implicit conversions. Here is an equivalent program with the conversions made explicit.

01
02
03
04
05
06
07
08
09
10
11
12
package algs11;
import stdlib.*;
public class Hello {
  public static void main (String[] args) {
    Integer i = Integer.valueOf (0);
    while (i.intValue () < 3) {
      StdOut.println ("Hello");
      int tmp = i.intValue () + 1;
      i = Integer.valueOf (tmp);
    }
  }
}}

In addition to having lots of extra function and method calls, this code potentially creates a bunch of objects. There are four separate objects, holding the values 0 through 3.

Conversion from base type to object type is called boxing. In the code above, this is achieved by the calls to Integer.valueOf.

Conversion from object type to base type is called unboxing. In the code above, this is achieved by the calls to i.intValue.

We will mostly only see code boxing integers and doubles. Here is a table summarizing the operations.

Base type Object type Boxing (base to object) Unboxing (object to base)
int base = 0; Integer object = null; object = Integer.valueOf(base); base = object.intValue();
double base = 0.0; Double object = null; object = Double.valueOf(base); base = object.doubleValue();

Java has five additional base types, as follows.

Base type Object type Boxing (base to object) Unboxing (object to base)
boolean base = false; Boolean object = null; object = Boolean.valueOf(base); base = object.booleanValue();
float base = 0.0F; Float object = null; object = Float.valueOf(base); base = object.floatValue();
byte base = 0; Byte object = null; object = Byte.valueOf(base); base = object.byteValue();
char base = 0; Character object = null; object = Character.valueOf(base); base = object.charValue();
short base = 0; Short object = null; object = Short.valueOf(base); base = object.shortValue();
long base = 0L; Long object = null; object = Long.valueOf(base); base = object.longValue();

Most compiled languages make an explicit distinction between object and base types. In C# they are called values types (declared with struct). Swift uses fancy compiler foo to get code that looks like python, but runs like Java.

Objects: Objects and equality [4/32]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
package algs11;
import stdlib.*;
import java.util.*;
public class Hello {
  public static void main (String[] args) {
    //Trace.showBuiltInObjects (true);
    //Trace.drawSteps ();
    //Trace.run ();
    Integer x = 3000;
    Integer y = 3000;
    StdOut.println ("x=" + x + ", y=" + y);
    StdOut.println ("                  x==y : " + (x == y));
    StdOut.println ("           x.equals(y) : " + (x.equals(y)));
    StdOut.println ("   Objects.equals(x,y) : " + (Objects.equals(x,y)));
  }
}

In Java, the == operator checks object identity on object types. That is, the two operands refer to the same object. More concretely: the two operands evaluate to the same address in memory.

Unlike other languages (such as C++) this behavior cannot be changed.

Objects all have an equals method. The behavior of equals varies from class to class. The default method, defined in java.lang.Object, tests identity, just like ==. Many of java's builtin classes override this default behavior to check value equality rather than object identity.

The java.util.Objects class provides some handy utilities, like Objects.equals. You can see the code here

Try some variations on java.lang.Integer

Try java.lang.Object

Try java.lang.String

Try arrays, with utility functions in java.util.Arrays

Recursion, Briefly: Recursion and collections [5/32]

Here's a nice way of thinking about recursion from the book Grokking Algorithms (online version)

Recursion, Briefly: Reading pure recursive functions [6/32]

A function is pure if it does not change any non-local variables, read files or network connections, or make any output.

Pure functions are like functions in math: they always do the same thing.

To understand the execution of a pure recursive function, it is easiest to start at the base case and work your way up.

01
02
03
04
05
  public static int f (int n) {
    if (n <= 0) return 1;
    int nMinus1 = f (n-1);
    return n * nMinus1;
  }

Bottom up (from the base case):

  f(0) = 1
  f(1) = 1 * f(0) = 1
  f(2) = 2 * f(1) = 2
  f(3) = 3 * f(2) = 6
  f(4) = 4 * f(3) = 24
  f(5) = 5 * f(4) = 120

Top down (from the initial argument):

  f(3) = 3 * f(2) 
       = 3 * (2 * f(1)) 
       = 3 * (2 * (1 * f(0)))
       = 3 * (2 * (1 * 1))

Recursion, Briefly: Reading pure recursive functions [7/32]

01
02
03
04
05
06
  public static int g (int n) {
    if (n <= 1) return n;
    int nMinus1 = g (n-1);
    int nMinus2 = g (n-2);
    return nMinus1 + nMinus2;
  }

Bottom up (from the base case):

  g(0) = 0
  g(1) = 1
  g(2) = g(0) + g(1) =  0 +  1 =  1
  g(3) = g(1) + g(2) =  1 +  1 =  2
  g(4) = g(2) + g(3) =  1 +  2 =  3
  g(5) = g(3) + g(4) =  2 +  3 =  5
  g(6) = g(4) + g(5) =  3 +  5 =  8
  g(7) = g(5) + g(6) =  5 +  8 = 13
  g(8) = g(6) + g(7) =  8 + 13 = 21
  g(9) = g(7) + g(8) = 13 + 21 = 34

Top down (from the initial argument):

  g(5) = g(3)                   + g(4)
       = (g(2)          + g(1)) + g(4)  
       = ((g(0) + g(1)) + g(1)) + g(4)
       = ((0    + 1   ) + 1   ) + g(4)
       = 2                      + g(4)
       = 2                      + g(3)                   + g(2)
       = 2                      + (g(2)          + g(1)) + g(2)
       = 2                      + ((g(0) + g(1)) + g(1)) + g(2)
       = 2                      + ((0    + 1   ) + 1   ) + g(2)
       = 2                      + 2                      + g(2)         
       = 2                      + 2                      + (g(0) + g(1))
       = 2                      + 2                      + (0    + 1   )
       = 2                      + 2                      + 1
       = 5

You can view this as a call tree:

    g(5)
      + g(4)
      |   + g(3)
      |   |   + g(2)    
      |   |   |   + g(1)
      |   |   |   + g(0)
      |   |   + g(1)    
      |   + g(2)
      |       + g(1)
      |       + g(0)
      + g(3)
          + g(2)    
          |   + g(1)
          |   + g(0)
          + g(1)    

Induction: Is this function useful? [8/32]

01
02
03
04
05
06
public static int f (int x, int y) {
  while (false) {
    x++;
  }
  return x;
}

Degenerate loop 1

Induction: Is this function useful? [9/32]

01
02
03
04
05
06
public static int f (int x, int y) {
  while (true) {
    x++;
  }
  return x;
}

Degenerate loop 2

Induction: Is this function useful? [10/32]

01
02
03
04
05
06
07
public static int f (int x, int y) {
  while (y > 0) {
    x++;
    y--;
  }
  return x;
}

A useful loop.

Why is it useful? What does it do? How do you know?

invariant-progress

I will walk through the first part of these notes (also available here)

Induction: Is this function useful? [11/32]

01
02
03
04
05
06
07
08
09
public static boolean someTrue (boolean[] a) {
  boolean result = false;
  int i = 0;
  while (i < a.length) {
    if (a[i]) result = true;
    i++;
  }
  return result;
}

What about this?

Induction: Is this function useful? [12/32]

01
02
03
04
05
06
07
08
09
10
11
public static int f (boolean[] a) {
  int result = 0;
  while (someTrue (a)) {
    int i = StdRandom.uniform (a.length);
    if (a[i]) {
      a[i] = false;
      result++;
    }
  }
  return result;
}

Is it guaranteed to terminate?

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
package algs11;
import stdlib.*;
public class Hello {
  public static boolean someTrue (boolean[] a) {
    boolean result = false;
    int i = 0;
    while (i < a.length) {
      if (a[i]) {
        result = true;
        break;
      } 
      i++;
    }
    return result;
  }
  public static int f (boolean[] a) {
    int result = 0;
    while (someTrue (a)) {
      int i = StdRandom.uniform (a.length);
      Trace.draw ();
      if (a[i]) {
        a[i] = false;
        result++;
      }
    }
    Trace.draw ();
    return result;
  }
  public static void main (String[] args) {
    Trace.run ();
    f (new boolean[] {true, false, true, true, false});
    StdOut.println ("Hello");
  }
}

Code variations: Testing [13/32]

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
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");
  }
}

You must test your code to know whether it works!

This is function, along with a main method to test. The function is obviously wrong, with a trivial implementation. For this reason it is called a stub.

Typing in tests manually is very tedious and error prone.

Reading console output is very tedious and error prone.

There is some work to create good tests, but the reward is that you need never look at the output of the program again. If it passes the tests, then it works (with high confidence).

This kind of testing is very common. There are frameworks, such as JUnit, to help write such tests, but we will not be using them in this class.

The code uses formatting to print error. This is supported by printf and format functions. See here

Code variations: While loop version [14/32]

11
12
13
14
15
16
17
18
19
20
21
22
23
24
  public static int numFives (double[] list) {
    int i = 0;
    int result = 0;



    while (i < list.length) {
      if (list[i] == 5) {
        result++;
      }
      i = i + 1;
    }
    return result;
  }

For [5,11,5,5], the loop values (line 17) are

list==[5,11,5,5], i==0, result==0
list==[5,11,5,5], i==1, result==1
list==[5,11,5,5], i==2, result==1
list==[5,11,5,5], i==3, result==2
list==[5,11,5,5], i==4, result==3

More abstractly:

list[i..]==[5,11,5,5], result==0
  list[i..]==[11,5,5], result==1
     list[i..]==[5,5], result==1
       list[i..]==[5], result==2
        list[i..]==[], result==3

This is a while loop.

Execution enters the loop without first checking to see if it is necessary.

numFivesAIO-

Code variations: Recursive version (forward) [15/32]

11
12
13
14
15
16
17
18
19
20
21
22
23
24
  public static int numFives (double[] list) {
    int result = numFivesHelper (list, 0, 0);
    return result;
  }

  public static int numFivesHelper (double[] list, int i, int result) {
    if (i < list.length) {
      if (list[i] == 5) {
        result++;
      }
      result = numFivesHelper (list, i + 1, result); 
    }
    return result;
  }

For [5,11,5,5], the call tree is

call@3 ([5,11,5,5], 0)
  call@4 ([11,5,5], 1)
    call@5  ([5,5], 1)
      call@6  ([5], 2)
        call@7 ([], 3)
        retn@7 ([], 3) : 3
      retn@6  ([5], 2) : 3
    retn@5  ([5,5], 1) : 3
  retn@4 ([11,5,5], 1) : 3
retn@3 ([5,11,5,5], 0) : 3

(Abbreviating list and i as single parameter showing list[i..].)

Converted to a recursive function.

Note that we do not mutate i in the helper

Note that computation goes forwards. We forget the old values of i as we go forward.

This kind of recursion is called tail recursion: the recursive call is the last thing the function does before it returns.

There is a one-to-one correspondence between loops and tail-recursive functions. We can mechanically convert between these to forms. Compilers do it all the time.

numFivesAROF-

Code variations: Recursive version (backward) [16/32]

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
  public static int numFives (double[] list) {

    int result = numFivesHelper (list, 0);
    return result;
  }
  public static int numFivesHelper (double[] list, int i) {
    int result = 0;
    if (i < list.length) {
      result = numFivesHelper (list, i + 1); 
      if (list[i] == 5) {
        result++;
      }
    }
    return result;
  }

For [5,11,5,5], the call tree is

call@3 ([5,11,5,5])
  call@4 ([11,5,5])
    call@5  ([5,5])
      call@6  ([5])
        call@7 ([])
        retn@7 ([]) : 0
      retn@6  ([5]) : 1
    retn@5  ([5,5]) : 2
  retn@4 ([11,5,5]) : 2
retn@3 ([5,11,5,5]) : 3

The recursive call here is often referred to as the leap of faith.

The most important design choice for recursive functions is:

  • Forwards / backwards
numFivesAROB-

Code variations: Backwards and forwards [17/32]

11
12
13
14
15
16
17
18
19
20
21
22
  public static double sumUntil (double val, double[] list) {
    double result = sumUntilHelper (val, list, 0);
    return result;
  }
  public static double sumUntilHelper (double val, double[] list, int i) {
    double result = 0;
    if (i < list.length && list[i] != val) {
      result = sumUntilHelper (val, list, i + 1); 
      result = result + list[i];
    }
    return result;
  }

It is common for recursive functions to do work both forwards and backwards.

For val==5, list==[11,21,31,5,41], the call tree is

call@3 (5, [11,21,31,5,41])
   call@4 (5, [21,31,5,41])
      call@5 (5, [31,5,41])
         call@6 (5, [5,41])
          ret@6 (5, [5,41]) : 0
       ret@5 (5, [31,5,41]) : 31
    ret@4 (5, [21,31,5,41]) : 52
 ret@3 (5, [11,21,31,5,41]) : 63
sumUntilARO-

Here is the complete starter code for this example:

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
41
package algs11;
import java.util.Arrays;
import stdlib.*;
public class Playground {
  /* Return the sum of the values in the list up to, but no including the first 5.0 */
  public static double sumUntil (double val, double[] list) {
    return StdRandom.uniform (); //TODO: fix this
  }
  /* This is a test function */
  public static void testSumUntil (double expected, double val, double[] list) {
    double actual = sumUntil (val, list);
    if (expected != actual) {
      StdOut.format ("Failed: Expecting [%f] Actual [%f] with argument (%f, %s)\n", expected, actual, val, Arrays.toString (list));
    }
  }
  /* A main function for testing */
  public static void main (String[] args) {
    for (double v : new double[] { 5, 7 }) {
      testSumUntil (63, v, new double[] { 11, 21, 31, v, 41 });
      testSumUntil (0, v, new double[] { v, 11, 21, 31, 41 });
      testSumUntil (104, v, new double[] { 11, 21, 31, 41, v });
      testSumUntil (11, v, new double[] { 11, v, 21, v, 31, 41 });
      testSumUntil (0, v, new double[] { v });
      testSumUntil (0, v, new double[] { v, v });
      testSumUntil (104, v, new double[] { 11, 21, 31, 41 });
      testSumUntil (11, v, new double[] { 11 });
      testSumUntil (0, v, new double[] {});
    }
    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 ("sumUntil");
    //Trace.drawStepsOfMethod ("sumUntilHelper");
    //Trace.run ();
    double[] list = new double[] { 11, 21, 31, 5, 41 };
    double result = sumUntil (5, list);
    StdOut.println ("result: " + result);
  }
}

Common mistakes: Starter code [18/32]

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);
  }
}

Common mistakes: Does this work? [19/32]

01
02
03
04
05
06
07
  public static int numFives (double[] a) {
    int result = 0;
    for (int i=0; i<a.length; i++)
      if (a[i] == 5.0)
        result++;   
    return result;
  }

Common mistakes: Does this work? [20/32]

01
02
03
04
05
06
07
08
  public static int numFives (double[] a) {
    double[] list = new double[] { 4, 5, 6, 5, 3 };
    int result = 0;
    for (int i=0; i<list.length; i++)
      if (list[i] == 5.0)
        result++;   
    return result;
  }

Common mistakes: Does this work? [21/32]

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

Common mistakes: Does this work? [22/32]

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

Common mistakes: Does this work? [23/32]

01
02
03
04
05
06
07
  public static int numFives (double[] a) {
    int result = 0;
    for (int i=0; i<a.length; i++)
      if (i == 5.0)
        result++;   
    return result;
  }

Common mistakes: Does this work? [24/32]

01
02
03
04
05
06
07
  public static int numFives (double[] a) {
    int result = 0;
    for (int i=0; i<a.length; i++)
      if (a == 5.0)
        result++;   
    return result;
  }

Common mistakes: Does this work? [25/32]

01
02
03
04
05
06
07
  public static int numFives (double[] a) {
    int result = 0;
    for (int i=0; 0<a.length; i++)
      if (a[i] == 5.0)
        result++;   
    return result;
  }

Common mistakes: Does this work? [26/32]

01
02
03
04
05
06
07
  public static int numFives (double[] a) {
    int result = 0;
    for (int i=0; i>0; i++)
      if (a[i] == 5.0)
        result++;   
    return result;
  }

Common mistakes: Does this work? [27/32]

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);
  }

Here the helper function has the same name as the starter function.

This is okay. It is called overloading in Java.

We often refer to a method by its name, but Java actually identifies the method using its name and the types of its parameters. So numFives_double[] is different from numFives_double[]_int_int.

Common mistakes: Does this work? [28/32]

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);
  }

Common mistakes: Does this work? [29/32]

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;
  }

Common mistakes: Does this work? [30/32]

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;
  }

Common mistakes: Does this work? [31/32]

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;
    }   
  }

Common mistakes: Does this work? [32/32]

01
02
03
04
05
06
07
  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++;
    return result;  
  }


Revised: 2008/03/17 13:01