# SICP: Why does this recursion-based sine approximation work?

Here is the question and solution to Structure and Interpretation of Computer Programs' exercise 1.15 (see here). My problem is, I don't know how the combination of these formulae actually work:

$$sin(x) = 3sin(x/3) - 4sin^3(x/3)$$ and $$sin(x) = x$$ for small $x$ radian values.

I understand the idea that the closer the radian angle gets to zero, the more it approximates the sine of that angle. I've seen excellent explanations (MIT OCW, Khan Academy). I also have worked out how the $sin(3x)= 3sin(x) - 4sin^3(x)$ formula is derived. But how are they being used together to derive an answer to $sin(x)$? The p function seems to simply be taking the variable angle divided by $3$ each recursive pass until angle is down below $0.1$ Then on the way back, we perform p as many times as we had to divide by $3$. So it seems $$sin(x) = 3sin(x/3) - 4sin^3(x/3)$$ magically becomes the same as $$sin(x) = 3(x) - 4(x^3)$$ through recursive application. How? I'm not very deeply versed in recursion theory. Also, if this is logarithmically getting closer to $0.1$, it's not as if we're totaling up lots of small $x$'s a la integration. This seems to be doing something vaguely like the Y-combinator -- which I also don't grasp that well yet.

Also, when we see the recursive steps (recursion) repeatedly dividing angle by $3$, what tells you definitively this is logarithmic? I mean, it looks like it's taking those giant order of magnitude leaps at each division, but is there another analytical way to call this logarithmic reduction?

There are two methods that this exercise uses. The first method is the $$p$$ function,

$$p(x) = 3x - 4x^3,$$

and the second is an approximation of sine, given by

$$\sin(x) \approx x.$$

The connection between the $$p$$ function and sines is that $$p(\sin(x/3)) = \sin x$$. This is a trigonometric identity (that one can prove by examining $$e^{3ix} = (e^{ix})^3$$, expanding via $$e^{i \theta} = \cos \theta + i \sin \theta$$, and considering imaginary parts).

The approximation $$\sin(x) \approx x$$ is more accurate when $$x$$ is smaller. In fact, the error of this approximation can be bounded by $$x^3/6$$, so this becomes a very good approximation for very small $$x$$.

The idea of this exercise is to repeatedly apply the $$p$$ map until evaluating $$\sin(x)$$ can be expressed in terms of a (possibly complicated polynomial) evaluated at $$\sin(y)$$ for some much smaller $$y$$, specifically a $$y$$ of the form $$y = x/3^n$$.

Let's work this through explicitly. We want to evaluate $$\sin x$$.

• If $$x$$ is small enough, we say $$\sin x \approx x$$ and we're done.
• If not, then we note that $$\sin x = p (\sin(x/3))$$. Now the relevant sine computation is $$\sin(x/3)$$.
• If $$x/3$$ is small enough, we use $$\sin(x/3) \approx (x/3)$$ to get that $$\sin x = p(\sin(x/3)) \approx p(x/3)$$.
• If not, then we use $$\sin (x/3) = p(\sin(x/3^2))$$ to see that $$\sin x = p(p(\sin(x/3^2))$$. Now the relevant sine computation is $$\sin(x/3^2) = \sin(x/9)$$.
• If $$x/3^2$$ is small enough, we use $$\sin(x/9) \approx x/9$$ to get that $$\sin x = p(p(\sin(x/9)) \approx p(p(x/9))$$.

Notice that the structure of this answer and the structure of the lisp code in the exercise are very similar. Iterating, the key recursive identity is that $$\sin x = p^{(n)}(\sin (x/3^n))$$, where $$p^{(n)}$$ means to iterate the $$p$$ map $$n$$ times.