Сумма ряда (рекурсия)

[Kirill43rus]

Не могу понять, как решить задачу с помощью рекурсии.
Пусть x1=x2=x3=1; xi=x(i-1)+x(i-3); i=4,5...
Найти сумму от i=1 до i=100 xi/2^i
Из наработок:
1) нахождение xi с помощью рекурсии:

PHP код:

int xi(int i)
{
    if (i < 0) return 0;
    if ((i == 0) || (i == 1) || (i == 2)) return 1;
    return xi(i-1) + xi(i-3);
} 


2) возведение в степень с помощью рекурсии:

PHP код:

double power(double x, double n) 
{
    if(n==0) return 1;
    if(n<0) return power(1.0/x,--n);
    return x*power(x,n-1);
} 


А вот дальше не знаю как их объеденить и найти сумму.

[GetMax]

А вот дальше не знаю как их объеденить и найти сумму.

   public double summa()
        {
            double sum = 0;
            for (int i = 0; i < 100; i++)
            {
                sum += xi(i) / power(2, i);
            }
            return sum;
        }

Хотя я и не уверен что double вместит в себя 2^100

[Kirill43rus]

Проблема в том, что циклом пользоваться нельзя. Нужно решить эту заадачу только с помощью рекурсии.

[GetMax]

Нужно решить эту заадачу только с помощью рекурсии.

  public double RecursSumma(int ii)
        {

            if (ii == 0) return 1;
            else
                return RecursSumma(ii-1) + (xi(ii) / power(2,ii));
        }

[Kirill43rus]

Препод полностью забраковал эту программу. Решение задачи должно быть в одной функции, ну с этим я как-нибудь сам разберусь.
Помощь нужна в этой части:

PHP код:

int xi(int i) 
{ 
    if (i < 0) return 0; 
    if ((i == 0) || (i == 1) || (i == 2)) return 1; 
    return xi(i-1) + xi(i-3); 
} 


При вычислении xi функция каждый раз вычисляет xi-1 и xi-3. Нужно сделать чтобы функция сохраняла каждое значение xi и при вычислении использовала его.

[Kirill43rus]

Вот функция для проверки рекурсии через цикл:

PHP код:

double funkcia(int n)
{
    int i;
    double *x;
    float tmp, sum=0;
    x=(double *)calloc(n, sizeof(double));
    x[0]=x[1]=x[2]=1;
    for(i=3; i<n; i++)
    {
        x[i]=x[i-1]+x[i-3];
    }
    for (i=0; i<n; i++)
    {
        tmp = x[i] / pow(2.0,i+1);
        sum += tmp;
    }
    return sum;
} 


[Jharvest]

Какие модули нужно подключать ???