CSC300 / CSC402: Recursive version (backward) [9/14] Previous pageContentsNext page

Recursion is more general than looping!

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 computation is:

//         list[i..]==[], result==0
//        list[i..]==[5], result==1
//      list[i..]==[5,5], result==2
//   list[i..]==[11,5,5], result==2
// list[i..]==[5,11,5,5], result==3

The call/return pattern 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 immediate recursive call here is often referred to as the leap of faith.

You're assuming you can solve the problem for the rest of the list.

Previous pageContentsNext page