Recursive algorithm for cos taylor series expansion c++

Question

I recently wrote a Computer Science exam where they asked us to give a recursive definition for the cos taylor series expansion. This is the series

cos(x) = 1 - x^2/2! + x^4/4! + x^6/6! ...

and the function signature looks as follows

float cos(int n , float x)

where n represents the number in the series the user would like to calculate till and x represents the value of x in the cos function

I obviously did not get that question correct and I have been trying to figure it out for the past few days but I have hit a brick wall

Would anyone be able to help out getting me started somewhere ?

Answer 1

All answers so far recompute the factorial every time. I surely wouldn't do that. Instead you can write :

float cos(int n, float x)
{
    if (n > MAX)
         return 1;
    return 1 - x*x / ((2 * n - 1) * (2 * n)) * cos(n + 1, x);
}

Consider that cos returns the following (sorry for the dots position) :

You can see that this is true for n>MAX, n=MAX, and so on. The sign alternating and powers of x are easy to see.

Finally, at n=1 you get 0! = 1, so calling cos(1, x) gets you the first MAX terms of the Taylor expansion of cos.

By developing (easier to see when it has few terms), you can see the first formula is equivalent to the following :

For n > 0, you do in cos(n-1, x) a division by (2n-3)(2n-2) of the previous result, and a multiplication by x². You can see that when n=MAX+1 this formula is 1, with n=MAX then it is 1-x²/((2MAX-1)2MAX) and so on.

If you allow yourself helper functions, then you should change the signature of the above to float cos_helper(int n, float x, int MAX) and call it like so :

float cos(int n, float x) { return cos_helper(1, x, n); }

---

Edit : To reverse the meaning of n from degree of the evaluated term (as in this answer so far) to number of terms (as in the question, and below), but still not recompute the total factorial every time, I would suggest using a two-term relation.

Let us define trivially cos(0,x) = 0 and cos(1,x) = 1, and try to achieve generally cos(n,x) the sum of the n first terms of the Taylor series.

Then for each n > 0, we can write, cos(n,x) from cos(n-1,x) :

cos(n,x) = cos(n-1,x) + x²ⁿ / (2n)!

now for n > 1, we try to make the last term of cos(n-1,x) appear (because it is the closest term to the one we want to add) :

cos(n,x) = cos(n-1,x) + x² / ((2n-1)2n) * ( x^2n-2 / (2n-2)! )

By combining this formula with the previous one (adapting it to n-1 instead of n) :

cos(n,x) = cos(n-1,x) + x² / ((2n-1)2n) * ( cos(n-1,x) - cos(n-2,x) )

We now have a purely recursive definition of cos(n,x), without helper function, without recomputing the factorial, and with n the number of terms in the sum of the Taylor decomposition.

However, I must stress that the following code will perform terribly :

• performance wise, unless some optimization allows to not re-evaluate a cos(n-1,x) that was evaluated at the previous step as cos( (n-1) - 1, x)
• precision wise, because of cancellation effects : the precision with which we get x^2n-2 / (2n-2)! is very bad

Now this disclaimer is in place, here comes the code :

float cos(int n, float x)
{
    if (n < 2)
        return n;
    float c = x * x / (2 * (n - 1) * 2 * n);
    return (1-c) * cos(n-1, x) + c * cos(n-2, x);
}