Question

Построить и записать алгоритм вычисления cos(x) для действительного числа x с точностью ε с использованием рекурсии

Answer 1

Cos(2x) = 2 cos(x) cos(x) - 1
cos(x) = 1 - x^2/2 + x^4/24 - x^6/720 + ...
1 - cos(2x) = 2 sin(x) sin(x)
sin(x) < 2 x / Pi

| 1 - cos(2x) | < 2 (2x/Pi)^2 = 8 x^2 / Pi^2
Если x^2 < Pi^2 eps / 8, то |1-cos(2x)|<eps

Предложение: делаем рекурсивный спуск по формуле cos(x)=2cos(x/2)^2 - 1, пока x > Pi sqrt(eps)/2, затем возвращаем 1-x^2/2. Оценка x < Pi sqrt(eps)/2 делалась для неравенства |1 - cos(x)| < eps, но возвращаем не просто 1, а 1-x^2/2 — до квадратичного члена, то есть с большей точностью. Кстати, Pi/2 < 2.
Код JavaScript
function cos1(x, eps)
{   if(Math.abs(x) < 2*Math.sqrt(eps)) return (1-x*x/2);  
var c = cos1(x/2, eps);  
return (2*c*c - 1);
} cos(0.5, 0.001);

Внимательно посмотрев на эту реализацию, можно увидеть хвостовую рекурсию, которую можно представить в виде цикла, что предпочтительнее, потому что не требует памяти под стек вызовов и потому является быстрее. Но это выходит за пределы рассматриваемой задачи.

P.S. Оценка рядом Маклорена-Тейлора при малых аргументах предпочтительнее: сходится быстрее.


другой вариант
Можно посчитать по ряду Тейлора, стандартно превратив итерацию в хвостовую рекурсию. Для этого используется вспомогательная функция, которой в качестве дополнительных (по сравнению с изначальной функцией) аргументов передаются все величины, которые хочется помнить (в данном случае номер члена i, очередной член a и вычисленную сумму s).

Код Haskell
cos' eps x = helper 1 1 0  
  where helper i a s          
   | abs a < eps   = s        
     | otherwise     = helper (i + 2) newa (s + a)              
   where newa = - a * x^2 / (i * (i + 1))

ряд Тейлора в данном случае удовлетворяет признаку Лейбница (ну, с оговорками), поэтому можно останавливаться, когда очередной член стал меньше эпсилона.
Код JavaScript
<script type="text/javascript"> function Cosine(x,eps)
{     function CosTaylor(x,n,an)  
  {         var an1 = (-1)*an*x*x/(2*n*(2*n-1));        
  if (Math.abs(an1) < eps) return an + an1;        
else          
  { return an + CosTaylor(x,n+1,an1); }  
  }      
return CosTaylor(x,1,1); }
</script>   <button onclick="alert( Cosine(0.75,0.001) )">Пример для x=0.75 и eps=0.001</button>

Answer 2

Algorithm for Computing cos(x) with Recursion

To compute the cosine of a real number x with a given precision ε using recursion, you can use the Taylor series expansion of the cosine function. The Taylor series expansion for cosine is as follows:

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

Here's an algorithm to compute cos(x) with recursion:

1. Define a recursive function `cos_recursive(x, n)` that takes two parameters: the value of x and the number of terms to consider in the Taylor series expansion. 2. If the number of terms `n` is 0, return 1 (the first term of the series). 3. Otherwise, compute the next term of the series using the formula `(-1)^n * (x^(2n) / (2n)!)`. 4. Recursively call `cos_recursive(x, n-1)` to compute the sum of the remaining terms. 5. Return the sum of the current term and the sum of the remaining terms.

Here's the algorithm in Python:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

def cos_recursive(x, n):
    if n == 0:
        return 1
    else:
        term = ((-1)  n) * (x  (2 * n)) / factorial(2 * n)
        return term + cos_recursive(x, n-1)

x = 1.0  # The value of x
epsilon = 0.0001  # The desired precision

n = 0
cos_value = cos_recursive(x, n)
while abs(cos_value - cos(x)) > epsilon:
    n += 1
    cos_value = cos_recursive(x, n)

print(f"The cosine of {x} is approximately {cos_value} with a precision of {epsilon}.")

This algorithm calculates the cosine of x using the Taylor series expansion until the desired precision ε is achieved. The `factorial` function is used to compute the factorial of a number, which is needed to calculate the terms of the series.

Please note that the code provided is a general algorithm and may require further optimization or adjustments depending on the programming language or specific requirements of your implementation.