CSC300 / CSC402: Recursive version (forward) [7/14] Previous pageContentsNext page

Replacing a while loop with a recursive function call:

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

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

The call/return pattern 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 forward. 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's no work to do after the recursive call 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.

In the language I work in, Scala, the compiler can be instructed to expect to be able to do tail-call elimination.

Previous pageContentsNext page