code review - Numerical Integration Via Adaptive Simpson's Method

I have written a code that uses the Adaptive Simpson's method to approximate integration. For those who are unaware of this Adaptive Simpson's method; Adaptive Simpson's method

In my code, I count the number of function evaluations are needed. I am wondering if there is a way to reduce the number of function evaluations needed but still retaining the same outputs and error. Here is my code:

Simpson[f_, a_, b_, er_] := Module[{s1, s2, h2, h = (b - a)/2},

 s1 = h (f[a] + 4 f[a + h] + f[b])/3;
 h2 = h/2;
 s2 = h2 (f[a] + 4 f[a + h2] + 2 f[a + h] + 4 f[b - h2] + f[b])/3;


 If[Abs[s1 - s2]/15 < er, s2 + (s2 - s1)/15,
  Simpson[f, a, a + h, er/2] + Simpson[f, a + h, b, er/2]]];
count = 0;
h[x_] := Module[{}, count++; 3 Sqrt[x]];
N[Simpson[h, 0, 1, 10.^-5] - 2]
count

For example, when approximating the integral of $3*sqrt(x)$ from 0 to 1, my algorithm makes 312 function calls of the function h, but I suspect some of these evaluations are repeated.

Answer

With a simple modification to your code

Simpson[f_, a_, b_, er_] := 
  Module[{s1, s2, h2, h = (b - a)/2}, 
   s1 = h (f[a] + 4 f[a + h] + f[b])/3;
   h2 = h/2;
   s2 = h2 (f[a] + 4 f[a + h2] + 2 f[a + h] + 4 f[b - h2] + f[b])/3;
   If[Abs[s1 - s2]/15 < er, s2 + (s2 - s1)/15, 
    Simpson[f, a, a + h, er/2] + Simpson[f, a + h, b, er/2]]];
count = 0;
h[x_] := Module[{}, Sow[x]; count++; 3 Sqrt[x]];

{result, xvalues} = Reap[N[Simpson[h, 0, 1, 10.^-5] - 2]];
{Length[Union[Flatten[xvalues]]], count}
(* {81, 312} *)

we can see that indeed your code evaluates h 312 times but at only 81 distinct values.

If the execution time of the integration is dominated by evaluating h this is clearly undesirable. A simple fix is to use "memoisation". This avoids re-evaluating h for values of x where it has already been computed. This can easily be done by using a definition for h such as

h[x_]:=h[x]= 3 Sqrt[x]

There is a very clear discussion of this in the Mathematica documentation https://reference.wolfram.com/language/tutorial/FunctionsThatRememberValuesTheyHaveFound.html