# 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]

• Read chapter 2 of Core Java for the Impatient.

• Skim section 1.3 of Algorithms

One of the problems is to convert mickey mouse:

to mickey moose:

This is an example of a Fractal also known as a Recursive drawing

 Objects: What is memory? [2/32]

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

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)
0xbeef00900xface0000@1.args
0xbeef00880xface0010@1.list

 0xbeef0080 ?? @2.overhead 0xbeef0078 0xface0010 @2.a 0xbeef0070 3 @2.i 0xbeef0068 2 @2.result
0xface00385.0Array.data[3]
0xface00305.0Array.data[2]
0xface002811.0Array.data[1]
0xface00205.0Array.data[0]
0xface00184Array.length

 0xface0008 0 Array.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`.

• For methods, the overhead includes the return address. This tells the machine what code should be executed when the method returns. If you are interested, you can read more.
• For objects, the overhead indicates the runtime type of the object. This is used to implement runtime type queries, such as the `getClass()` method. If you are interested, you can read more.

 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

• ```int x = 3000;
int y = 3000;```
• ```Integer x = 3000;
Integer y = 3000;```
• ```Integer x = 30;
Integer y = 30;```
• ```Integer x = Integer.valueOf(3000);
Integer y = Integer.valueOf(3000);```
• ```Integer x = Integer.valueOf(30);
Integer y = Integer.valueOf(30);```
• ```Integer x = new Integer(3000);
Integer y = new Integer(3000);```
• ```Integer x = new Integer(30);
Integer y = new Integer(30);```
• ```Integer x = 3000;
Integer y = x;```
• ```Integer x = 3000;
Integer y = null;```
• ```Integer x = null;
Integer y = 3000;```
• ```Object x = new Object();
Object y = new Object();```
• ```String x = "Hello";
String y = "Hello";```
• ```String x = new String ("Hello");
String y = new String ("Hello");```
• ```String x = "Hel" + "lo";
String y = "Hel" + "lo";```
• ```String a = new String ("Hello");
String b = new String ("Hello");
String x = a.intern();
String y = b.intern();```

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

• ```int[] x = new int[] { 11, 21, 31 };
int[] y = new int[] { 11, 21, 31 };```
• ```int[] x = { 11, 21, 31 };
int[] y = { 11, 21, 31 };```
• ```Integer[] x = new Integer[] { 11, 21, 31 };
Integer[] y = new Integer[] { 11, 21, 31 };```
• ```int[][] x = new int[][] { { 11, 21, 31 }, { 12, 22, 32 } };
int[][] y = new int[][] { { 11, 21, 31 }, { 12, 22, 32 } };```
• ```Integer[][] x = new Integer[][] { { 11, 21, 31 }, { 12, 22, 32 } };
Integer[][] y = new Integer[][] { { 11, 21, 31 }, { 12, 22, 32 } };```
• ```StdOut.println ("x=" + Arrays.toString(x) + ", y=" + Arrays.toString(y));
StdOut.println ("    Arrays.equals(x,y) : " + (Arrays.equals(x,y)));
StdOut.println ("Arrays.deepEquals(x,y) : " + (Arrays.deepEquals(x,y)));```

 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)
```
• `g(5)` calls `g(4)` and `g(3)`.
• `g(4)` calls `g(3)` and `g(2)`.
• etc.

 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?

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

 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.

 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.

 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

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

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

 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

 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

 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

 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

 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

 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

 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.

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