迭代与递归函数计算序列第100项结果不一致，是精度问题吗？

我要计算序列 $x_0=1 ; x_i=\dfrac{x_{i-1}+1}{x_{i-1}+2}, i=1,2, \ldots$ 的第100项，编写了迭代函数l()和递归函数r()，但两者输出结果不一致——迭代结果为0.618034，递归结果为0.666667。想问这是由于小数精度丢失导致的吗？

驱动代码 #

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() #

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

递归函数r() #

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

输出结果 #

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

问题原因分析 #

这不是小数精度丢失导致的，而是递归函数的逻辑完全错误：

你在main中调用r(x_0)时，x_0的值是1.0，递归执行流程如下：

1. 第一次调用r(1.0)，进入else分支，调用r(0.0)
2. r(0.0)触发基准条件，返回1
3. 回到r(1.0)，计算(1 + 1)/(1 + 2) = 2/3 ≈ 0.666667并返回

也就是说，这个递归函数只完成了1次迭代，根本没有计算到序列的第100项。而迭代函数l()是循环了100次（i从data.txt读取的是100），所以得到的是正确的第100项结果。

修正后的递归函数 #

正确的递归函数应该接收迭代次数n作为参数，而非当前的x值，示例如下：

double r(int n)
{
    if (n == 0)
        return 1.0; // 对应x0的初始值
    else {
        double prev = r(n-1);
        return (prev + 1)/(prev + 2);
    }
}

在main中调用r(100)，就能和迭代函数得到一致的结果。

内容的提问来源于stack exchange，提问作者Maroon Racoon