CSC300: Backwards and forwards [9/13] Previous pageContentsNext page

11
12
13
14
15
16
17
18
19
20
21
22
  public static double sumUntil (double val, double[] list) {
    double result = sumUntilHelper (val, list, 0);
    return result;
  }
  public static double sumUntilHelper (double val, double[] list, int i) {
    double result = 0;
    if (i < list.length && list[i] != val) {
      result = sumUntilHelper (val, list, i + 1); 
      result = result + list[i];
    }
    return result;
  }

It is common for recursive functions to do work both forwards and backwards.

For val==5, list==[11,21,31,5,41], the call tree is

call@3 (5, [11,21,31,5,41])
   call@4 (5, [21,31,5,41])
      call@5 (5, [31,5,41])
         call@6 (5, [5,41])
          ret@6 (5, [5,41]) : 0
       ret@5 (5, [31,5,41]) : 31
    ret@4 (5, [21,31,5,41]) : 52
 ret@3 (5, [11,21,31,5,41]) : 63

Here is the complete starter code for this example:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package algs11;
import java.util.Arrays;
import stdlib.*;
public class Playground {
  /* Return the sum of the values in the list up to, but no including the first 5.0 */
  public static double sumUntil (double val, double[] list) {
    return StdRandom.uniform (); //TODO: fix this
  }
  /* This is a test function */
  public static void testSumUntil (double expected, double val, double[] list) {
    double actual = sumUntil (val, list);
    if (expected != actual) {
      StdOut.format ("Failed: Expecting [%f] Actual [%f] with argument (%f, %s)\n", expected, actual, val, Arrays.toString (list));
    }
  }
  /* A main function for testing */
  public static void main (String[] args) {
    for (double v : new double[] { 5, 7 }) {
      testSumUntil (63, v, new double[] { 11, 21, 31, v, 41 });
      testSumUntil (0, v, new double[] { v, 11, 21, 31, 41 });
      testSumUntil (104, v, new double[] { 11, 21, 31, 41, v });
      testSumUntil (11, v, new double[] { 11, v, 21, v, 31, 41 });
      testSumUntil (0, v, new double[] { v });
      testSumUntil (0, v, new double[] { v, v });
      testSumUntil (104, v, new double[] { 11, 21, 31, 41 });
      testSumUntil (11, v, new double[] { 11 });
      testSumUntil (0, v, new double[] {});
    }
    StdOut.println ("Finished tests");
  }
  /* A main function for debugging -- change the name to "main" to run it */
  public static void main2 (String[] args) {
    //Trace.drawSteps ();
    //Trace.drawStepsOfMethod ("sumUntil");
    //Trace.drawStepsOfMethod ("sumUntilHelper");
    //Trace.run ();
    double[] list = new double[] { 11, 21, 31, 5, 41 };
    double result = sumUntil (5, list);
    StdOut.println ("result: " + result);
  }
}

Previous pageContentsNext page