CSC300: Code variations: Recursive version (optimistic, backward) [20/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) {

    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

Previous pageContentsNext page