CSC300 / CSC402: Backwards and forwards [10/14] Previous pageContentsNext page

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

Try going through this example yourself.

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

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