CSC300: Code variations: Recursive version (cautious, forward) [18/37] Previous pageContentsNext page

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.

Previous pageContentsNext page