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