实现法雷序列时遇到特殊的「递归深度超出限制」错误

我编写了一个基于法雷序列的程序，用于将输入值x转换为最简分数。但输入0.1111111111时会触发递归深度超限错误：

farey(l, m, a2, b2, x, iterations+1)
[Previous line repeated 988 more times]
RecursionError: maximum recursion depth exceeded

但输入更长的数值（如0.111111111111111111111111111111）时，程序能正常输出1/9。

Python代码如下：

def farey(a1, b1, a2, b2, x, iterations):
    l = a1 + a2
    m = b1 + b2
    f = l/m

    if iterations == 100000:
        print(str(l) + "/" + str(m))
        return 0

    if x > f:
        farey(l, m, a2, b2, x, iterations+1)
    elif x < f:
        farey(a1, b1, l, m, x, iterations+1)
    else:
        print(str(l) + "/" + str(m))
        return 0


farey(0, 1, 1, 1, 0.1111111111, 0)

我将代码移植到C后表现完全一致，说明问题出在逻辑上。在Python中设置sys.setrecursionlimit(100000)也无效，C代码如下：

#include <iostream>
typedef unsigned long long ull;
using namespace std;


int farey(ull a1, ull b1, ull a2, ull b2, double x, unsigned int iterations) {
    double f = (double)(a1 + a2) / (b1 + b2);

    if (iterations == 100000){
        cout << a1 + a2 << "/" << b1 + b2;
        return 0;
    }

    if (x > f) {
        farey(a1+a2, b1+b2, a2, b2, x, iterations + 1);
    }
    else if (x < f) {
        farey(a1, b1, a1+a2, b1+b2, x, iterations + 1);
    } 
    else{
        cout << a1 + a2 << "/" << b1 + b2;
        return 0;
    }
}

int main()
{
    farey(0, 1, 1, 1, 0.1111111111, 0);
}

问题根源 #

核心问题出在浮点数精度误差和法雷序列迭代的特性：

1. 0.1111111111作为双精度浮点数，实际存储值略小于1/9（1/9≈0.1111111111111111）；而更长的输入字符串被解析后，更接近甚至等于双精度能表示的1/9近似值。
2. 法雷序列迭代中，程序会不断生成区间内的中间分数，比较x和中间分数f的大小。当x略小于1/9时，程序会持续向左迭代，但永远无法触发x == f的终止条件——因为每次生成的f都是有理数，而x是一个接近但不等于1/9的浮点数，最终导致递归超出深度限制。
3. 长输入的字符串解析后，浮点数刚好匹配双精度能表示的1/9近似值，迭代到1/9时触发终止条件，程序正常结束。

解决方案 #

1. 增加精度判断阈值 #

不要直接比较浮点数相等，而是判断两者差值是否小于极小阈值（如1e-12），避免精度误差导致的无限递归：
修改后的Python代码：

def farey(a1, b1, a2, b2, x, iterations):
    l = a1 + a2
    m = b1 + b2
    f = l/m
    epsilon = 1e-12

    if iterations == 100000:
        print(f"{l}/{m}")
        return

    if abs(x - f) < epsilon:
        print(f"{l}/{m}")
        return
    elif x > f:
        farey(l, m, a2, b2, x, iterations+1)
    else:
        farey(a1, b1, l, m, x, iterations+1)

farey(0, 1, 1, 1, 0.1111111111, 0)

C++版本：

#include <iostream>
#include <cmath>
typedef unsigned long long ull;
using namespace std;


int farey(ull a1, ull b1, ull a2, ull b2, double x, unsigned int iterations) {
    double f = static_cast<double>(a1 + a2) / (b1 + b2);
    const double epsilon = 1e-12;

    if (iterations == 100000){
        cout << a1 + a2 << "/" << b1 + b2;
        return 0;
    }

    if (fabs(x - f) < epsilon) {
        cout << a1 + a2 << "/" << b1 + b2;
        return 0;
    }
    else if (x > f) {
        farey(a1+a2, b1+b2, a2, b2, x, iterations + 1);
    }
    else {
        farey(a1, b1, a1+a2, b1+b2, x, iterations + 1);
    }
}

int main()
{
    farey(0, 1, 1, 1, 0.1111111111, 0);
}

2. 改用迭代实现替代递归 #

递归受限于语言的递归深度限制，改用循环迭代可彻底避免溢出问题，同时性能更优：
Python迭代版本：

def farey_iter(x):
    a1, b1 = 0, 1
    a2, b2 = 1, 1
    epsilon = 1e-12
    max_iter = 100000
    iterations = 0

    while iterations < max_iter:
        l = a1 + a2
        m = b1 + b2
        f = l / m

        if abs(x - f) < epsilon:
            print(f"{l}/{m}")
            return
        elif x > f:
            a1, b1 = l, m
        else:
            a2, b2 = l, m
        iterations += 1

    print(f"{l}/{m}")

farey_iter(0.1111111111)

C++迭代版本：

#include <iostream>
#include <cmath>
typedef unsigned long long ull;
using namespace std;

void farey_iter(double x) {
    ull a1 = 0, b1 = 1;
    ull a2 = 1, b2 = 1;
    const double epsilon = 1e-12;
    const unsigned int max_iter = 100000;
    unsigned int iterations = 0;

    while (iterations < max_iter) {
        ull l = a1 + a2;
        ull m = b1 + b2;
        double f = static_cast<double>(l) / m;

        if (fabs(x - f) < epsilon) {
            cout << l << "/" << m;
            return;
        } else if (x > f) {
            a1 = l;
            b1 = m;
        } else {
            a2 = l;
            b2 = m;
        }
        iterations++;
    }

    ull l = a1 + a2;
    ull m = b1 + b2;
    cout << l << "/" << m;
}

int main() {
    farey_iter(0.1111111111);
    return 0;
}

3. 直接处理字符串输入（可选） #

如果输入是字符串形式的小数，可先转换为分数（如0.1111111111转成1111111111/10000000000），再通过最大公约数约分，完全规避浮点数精度问题。

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