CSC300: Lecture 2 (Induction, Iteration and Recursion)

Contents [0/37]

Homework [1/37]
Recursion, Briefly: Recursion and collections [2/37]
Recursion, Briefly: Reading pure recursive functions [3/37]
Recursion, Briefly: Reading pure recursive functions [4/37]
Induction: Is this function useful? [5/37]
Induction: Is this function useful? [6/37]
Induction: Is this function useful? [7/37]
Induction: Is this function useful? [8/37]
Induction: Is this function useful? [9/37]
Induction: Linear search [10/37]
Induction: Binary search [11/37]
A basic setup: Testing [12/37]
A basic setup: Debugging [13/37]
A basic setup: How to write code [14/37]
Code variations: While loop version (optimistic) [15/37]
Code variations: Recursive version (optimistic, forward) [16/37]
Code variations: Loop version (cautious, forward) [17/37]
Code variations: Recursive version (cautious, forward) [18/37]
Code variations: Recursive version (cautious, backward) [19/37]
Code variations: Recursive version (optimistic, backward) [20/37]
Code variations: Recursive version (optimistic, forward) [21/37]
Code variations: Backwards and forwards [22/37]
Common mistakes: Starter code [23/37]
Common mistakes: Does this work? [24/37]
Common mistakes: Does this work? [25/37]
Common mistakes: Does this work? [26/37]
Common mistakes: Does this work? [27/37]
Common mistakes: Does this work? [28/37]
Common mistakes: Does this work? [29/37]
Common mistakes: Does this work? [30/37]
Common mistakes: Does this work? [31/37]
Common mistakes: Does this work? [32/37]
Common mistakes: Does this work? [33/37]
Common mistakes: Does this work? [34/37]
Common mistakes: Does this work? [35/37]
Common mistakes: Does this work? [36/37]
Common mistakes: Does this work? [37/37]

Homework [1/37]

Recursion, Briefly: Recursion and collections [2/37]

Here's a nice way of thinking about recursion from the book Grokking Algorithms

Recursion, Briefly: Reading pure recursive functions [3/37]

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 [4/37]

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? [5/37]

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? [6/37]

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? [7/37]

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? [8/37]

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? [9/37]

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
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++;
      }
    }
    return result;
  }
  public static void main (String[] args) {
    Trace.run ();
    f (new boolean[] {true, false, true, true, false});
    StdOut.println ("Hello");
  }
}

Induction: Linear search [10/37]

01
02
03
04
05
06
07
08
  public static boolean contains (double val, double[] list) {
    int i = 0;
    while (i < list.length) {
      if (val == list[i]) { return true; }
      i++;
    }
    return false;
  }

Another version

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

How long does it take (in the worst case)?

running-times

More graphs (also available here)

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
package algs11;
import java.util.Arrays;
import stdlib.*;

public class Playground {
  /* Return true if val is in the list */
  public static boolean contains (double val, double[] list) {
    return StdRandom.bernoulli (); //TODO: fix this
  }
  /* This is a test function */
  public static void testContains (boolean expected, double val, double[] list) {
    boolean actual = contains (val, list);
    if (expected != actual) {
      StdOut.format ("Failed: Expecting [%b] Actual [%b] 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 }) {
      testContains (true, v, new double[] { 11, 21, 31, v, 41 });
      testContains (true, v, new double[] { v, 11, 21, 31, 41 });
      testContains (true, v, new double[] { 11, 21, 31, 41, v });
      testContains (true, v, new double[] { 11, v, 21, v, 31, 41 });
      testContains (true, v, new double[] { v });
      testContains (true, v, new double[] { v, v });
      testContains (false, v, new double[] { 11, 21, 31, 41 });
      testContains (false, v, new double[] { 11 });
      testContains (false, v, new double[] {});
    }
    StdOut.println ("Finished tests");
  }
}

Induction: Binary search [11/37]

01
02
03
04
05
06
07
08
09
10
11
  public static boolean contains(double val, double[] list) {
    int lo = 0;
    int hi = list.length-1;
    while (hi >= lo) {
      int mid = lo + (hi-lo)/2;
      if (val > list[mid]) lo = mid + 1;
      if (val < list[mid]) hi = mid - 1;
      if (val == list[mid]) return true;
    }
    return false;
  }

A more complicated pattern. Does it terminate? Under what assumptions?

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
package algs11;
import java.util.Arrays;
import stdlib.*;

public class Playground {
  /* Return true if val is in the list */
  public static boolean contains (double val, double[] list) {
    return StdRandom.bernoulli (); //TODO: fix this
  }
  /* This is a test function */
  public static void testContains (boolean expected, double val, double[] list) {
    boolean actual = contains (val, list);
    if (expected != actual) {
      StdOut.format ("Failed: Expecting [%b] Actual [%b] with argument (%f, %s)\n", expected, actual, val, Arrays.toString (list));
    }
  }
  /* A main function for testing */
  public static void main (String[] args) {        
    testContains (true, 11, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (true, 21, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (true, 31, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (true, 41, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (true, 51, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (true, 61, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (true, 71, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (false, 10, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (false, 20, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (false, 30, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (false, 40, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (false, 50, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (false, 60, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (false, 70, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (false, 80, new double[] { 11, 21, 31, 41, 51, 61, 71 });        
    StdOut.println ("Finished tests");
  }
}

A basic setup: Testing [12/37]

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

A basic setup: Debugging [13/37]

01
02
03
04
05
06
07
08
09
10
11
  /* A main function for debugging -- change the name to "main" to run it */
  public static void main2 (String[] args) {
    //Trace.graphvizOutputFormat ("svg");
    //Trace.drawSteps ();
    //Trace.drawStepsOfMethod ("contains");
    //Trace.drawStepsOfMethod ("containsHelper");
    //Trace.run ();
    double[] list = new double[] { 5, 11, 5, 5 };
    boolean result = contains (5, list);
    StdOut.println ("result: " + result);
  }

This simple test will allow us to use the debugger to watch the program's execution.

Trace.run() causes the program to be run in a debugger.

Trace.drawStepsOfMethod("contains") causes a drawing to be created at every step of the contains method. The drawings will be created in a folder on your Desktop. To change the location, or for further discussion, see here.

A basic setup: How to write code [14/37]

The amount of time spent on a function does not amount to much. If you are not working effectively, you can spend months on a single function and never get it correct.

So how do you work efficiently? Key things:

Here is a step-by-step

  1. You need to work through some examples before you start. I've typically listed some examples for you. You should walk through these on paper and see what you expect.

  2. Don't do everything at once. Pick a part of the problem. Use a small, typical example. You can simplify things a bit to start. For example, suppose that the array is always nonempty.

  3. Think about how you would do it, on paper. Draw pictures of the state before and after. Once you have a picture, you can think what you need to do in this case to accomplish what you want.

  4. Write a test that will succeed if you get the code right and fail if you don't.

  5. Try to write some code to accomplish the task.

  6. If the code does not pass your test, use the DEBUGGER! Set a breakpoint and the start the debugger, or use the Trace class.

  7. Go back to step 3 and repeat 3-7 until the code works on your first example.

  8. What about other examples? Repeat steps 2-8 until your code is completely correct.

Code variations: While loop version (optimistic) [15/37]

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.

This is called optimistic: You jump into the loop without first testing that the list is non-empty.

numFivesAIO-

Code variations: Recursive version (optimistic, forward) [16/37]

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: Loop version (cautious, forward) [17/37]

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


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

    return result;
  }

For [5,11,5,5], the loop values (lines 17 and 24) are

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

Here, we first test that the list is non-empty, only entering the loop in this case. This is called cautious execution. We only enter the loop if we know it is necessary.

For both loops and tail-recursions, we can choose the style:

  • Optimistic / cautious

Beginning programmers often mix the cautious and optimistic styles. For loops this usually just causes redundant checks. For example, using a while loop in the example above, rather than a do loop.

numFivesAIC-

Code variations: Recursive version (cautious, forward) [18/37]

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

    if (list[i] == 5) {
      result++;
    }
    if (i + 1 < list.length) {
      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)
      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

Recursive version.

A common mistake is to write

         numFivesHelper (list, i + 1, result);

instead of:

result = numFivesHelper (list, i + 1, result);

Experienced programmers typically prefer the optimistic style --- it is less error prone. There is only one check, rather than two.

Beginning programmers often mix the cautious and optimistic styles. For recursions this often results in disaster --- usually a check is omitted, causing the code to crash.

For example, a beginner might write:

11
12
13
14
15
16
17
18
19
20
21
22
23
  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 (list[i] == 5) {
      result++;
    }
    if (i + 1 < list.length) {
      result = numFivesHelper (list, i + 1, result); 
    }
    return result;
  }

or:

11
12
13
14
15
16
17
18
19
20
21
22
  public static int numFives (double[] list) {
    if (list.length == 0) return 0;
    int result = numFivesHelper (list, 0, 0);
    return result;
  }
  public static int numFivesHelper (double[] list, int i, int result) {
    if (list[i] == 5) {
      result++;
    }
    result = numFivesHelper (list, i + 1, result); 
    return result;
  }

The first of these is the most problematic, since the error will only show up if you test the empty list. An error like this can slip into production code and cause applications to crash. In C-like languages, this kind of error can create a security problem: the application may not crash, but may exhibit undesirable behavior that a hacker can exploit.

numFivesARCF-

Code variations: Recursive version (cautious, backward) [19/37]

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
  public static int numFives (double[] list) {
    if (list.length == 0) return 0;
    int result = numFivesHelper (list, 0);
    return result;
  }
  public static int numFivesHelper (double[] list, int i) {
    int result = 0;
    if (i + 1 < 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])
      retn@6  ([5]) : 1
    retn@5  ([5,5]) : 2
  retn@4 ([11,5,5]) : 2
retn@3 ([5,11,5,5]) : 3

Recursive functions can also compute backwards. (In this case, they are not tail-recursive.)

numFivesARCB-

Here is a more compact version

11
12
13
14
15
16
17
18
19
20
21
22
  public static int numFives (double[] list) {
    if (list.length == 0) return 0;
    int result = numFivesHelper (list, 0);
    return result;
  }
  public static int numFivesHelper (double[] list, int i) {
    int result = (i + 1 >= list.length) ? 0 : numFivesHelper (list, i + 1); 
    if (list[i] == 5) {
      result++;
    }
    return result;
  }

Code variations: Recursive version (optimistic, backward) [20/37]

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

Here is the optimistic version.

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

The most important design choices for recursive functions are:

  • Forwards / backwards
  • Optimistic / cautious
numFivesAROB-

Code variations: Recursive version (optimistic, forward) [21/37]

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

The optimistic forward version, repeated for easy comparison.

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
numFivesAROF2-

Code variations: Backwards and forwards [22/37]

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 [23/37]

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? [24/37]

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? [25/37]

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? [26/37]

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? [27/37]

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? [28/37]

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? [29/37]

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? [30/37]

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? [31/37]

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? [32/37]

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? [33/37]

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? [34/37]

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? [35/37]

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? [36/37]

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? [37/37]

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