我可以从迭代函数和递归函数中获得不同的结果吗?

Can I obtain different results from iterative and recurive functions?

提问人:Maroon Racoon 提问时间:11/7/2022 最后编辑:Maroon Racoon 更新时间:11/7/2022 访问量:57

问:

我的代码应该计算序列的第 100 个元素$x_0=1 ; x_i=\dfrac{x_{i-1}+1}{x_{i-1}+2}, i=1,2, \ldots$

我写了迭代和递归函数,但结果不相等。是因为小数点丢失了吗?

这是我的驱动程序代码。文件中的数据为 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()是迭代函数,是递归函数r()


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);
}

以下是结果

100th element (by looping): 0.618034
100th element (by recursion): 0.666667
C++ 递归 序列 数值计算

评论

4赞 user4581301 11/7/2022
是的,如果编写代码不是为了产生相同的可观察行为。
2赞 Igor Tandetnik 11/7/2022
r不可能是对的。它没有提到任何地方。它只是运行递归,直到序列一直收敛到 ,所以嵌套调用总是返回 ,而顶级调用返回 。这就是你所观察到的。10001(1 + 1) / (1 + 2) == 2/3 == 0.666666
2赞 Pepijn Kramer 11/7/2022
任何递归算法都可以写成迭代算法:因此,任何服从的差异都是错误的结果。
0赞 Lukas-T 11/7/2022
...两者都不包含 . 似乎计算序列的第 1 个元素而不是第 100 个元素(尽管此处设置为 100)。该参数在 上完全缺失。l(x, i)100l(x, i)iir(x)
0赞 molbdnilo 11/7/2022
看起来您将序列的元素与它们的索引混淆了;的初始值为 1.0,但您将其与(索引)0 进行比较以确定何时停止。x

答:

6赞 Some programmer dude 11/7/2022 #1

I 你做的递归函数

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

这等于x == 1.0

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

这当然等于

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

由于将返回该等式是r(0)1

(1.0 + 1) / (1.0 + 2)

没有进一步的递归。结果是 .2.0 / 3.00.66667

另一方面,迭代函数将进行迭代,每次迭代都会改变 的值,使其越来越小。l100x

这些函数只是做不同的事情,导致不同的结果。