CSC300: Code variations: Recursive version (cautious, backward) [19/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);
    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.)

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

Previous pageContentsNext page