c++recursionsequencenumerical-computing

Can I obtain different results from iterative and recurive functions?


My code is supposed to calculate the 100th element of the sequence $x_0=1 ; x_i=\dfrac{x_{i-1}+1}{x_{i-1}+2}, i=1,2, \ldots$

I wrote iterative and recursive functions, but the results are not equal. Is it due to the lost of decimals?

Here is my driver code. The data from the file is i=100.

int main()
{
    int i;

    ifstream f ("data.txt");
    f >> i;

    double x_0= 1.00;

    double x_100 = l(x_0, i);

    ofstream g ("results.txt", ios::app);
    g <<"\n100th element (by looping): " << x_100;

    x_100 = r(x_0);
    g <<"\n100th element (by recursion): " << x_100;

 
   return 0;
}

l() is iterative function, r() is recursive function


double l(double x, int i)
{
    for (int j = 0; j<i ; j++){
            x = (x + 1)/(x+2);
    }
    return x;

}

double r(double x)
{
    if (x == 0)
        return 1;
    else
        return (r(x-1) + 1) / (r(x-1) + 2);
}

Here are the results

100th element (by looping): 0.618034
100th element (by recursion): 0.666667

Solution

  • I the recursive function you do

    (r(x-1) + 1) / (r(x-1) + 2)
    

    With x == 1.0 that's equal to

    (r(1-1) + 1) / (r(1-1) + 2)
    

    That's of course equal to

    (r(0) + 1) / (r(0) + 2)
    

    And since r(0) will return 1 that equation is

    (1.0 + 1) / (1.0 + 2)
    

    There's no further recursion. The result is 2.0 / 3.0 which is 0.66667.

    The iterative function l on the other hand will do 100 iterations where each iteration will change the value of x, making it even smaller and smaller.

    The functions simply does different things, leading to different results.