recursion - 调用此递归函数时如何避免堆栈溢出

我已经在Rust中实现了Ramer–Douglas–Peucker线简化算法，并且在epsilon值> 1.0时可以正常使用。但是，任何低于该值的值都会导致堆栈溢出。如何重写函数以避免这种情况？

// distance formula
pub fn distance(start: &[f64; 2], end: &[f64; 2]) -> f64 {
    ((start[0] - end[0]).powf(2.) + (start[1] - end[1]).powf(2.)).sqrt()
}

// perpendicular distance from a point to a line
pub fn point_line_distance(point: &[f64; 2], start: &[f64; 2], end: &[f64; 2]) -> f64 {
    if start == end {
        return distance(*&point, *&start);
    } else {

        let n = ((end[0] - start[0]) * (start[1] - point[1]) -
                 (start[0] - point[0]) * (end[1] - start[1]))
            .abs();
        let d = ((end[0] - start[0]).powf(2.0) + (end[1] - start[1]).powf(2.0)).sqrt();
        n / d
    }
}

// Ramer–Douglas-Peucker line simplification algorithm
pub fn rdp(points: &[[f64; 2]], epsilon: &f64) -> Vec<[f64; 2]> {
    let mut dmax = 1.0;
    let mut index: usize = 0;
    let mut distance: f64;
    for (i, _) in points.iter().enumerate().take(points.len() - 1).skip(1) {
        distance = point_line_distance(&points[i],
                                       &*points.first().unwrap(),
                                       &*points.last().unwrap());
        if distance > dmax {
            index = i;
            dmax = distance;
        }
    }
    if dmax > *epsilon {
        let mut intermediate = rdp(&points[..index + 1], &*epsilon);
        intermediate.pop();
        intermediate.extend_from_slice(&rdp(&points[index..], &*epsilon));
        intermediate
    } else {
        vec![*points.first().unwrap(), *points.last().unwrap()]
    }
}

fn main() {
    let points = vec![[0.0, 0.0], [5.0, 4.0], [11.0, 5.5], [17.3, 3.2], [27.8, 0.1]];
    // change this to &0.99 to overflow the stack
    let foo: Vec<_> = rdp(&points, &1.0);
    assert_eq!(foo, vec![[0.0, 0.0], [5.0, 4.0], [11.0, 5.5], [17.3, 3.2]]);
}

最佳答案

查看rdp的流程。这是一个递归函数，它以dmax > epsilon为条件进行递归。因此，在逐步操作时，请遵循以下变量:

首先，我们将dmax设置为1.0。然后，如果distance > dmax，dmax设置为distance。因此，dmax不可能小于1.0。

然后，如果是dmax > epsilon，我们递归。如果使用epsilon < 1.0，则将始终发生这种情况。

如果我们查看wikipedia上的算法，您会看到dmax应该从0.0开始。

顺便说一句，您可以使用hypot函数使distance函数更好一些。