Rust递归函数如何在不改为循环的情况下减少栈空间占用？

问题背景 #

我有一段运行一段时间后会抛出栈溢出错误的代码，经排查不是无限递归，而是深度有限但效率低下的递归问题。核心代码如下：

fn get_descendant_leaves(&self, p: Point) -> Vec<Point> {
    let children = self.get_children(p);
    if children.is_empty() {
        vec![p]
    } else {
        children
            .iter()
            .map(|child_p| self.get_descendant_leaves(child_p.0))
            .flatten()
            .collect()
    }
}

注：函数中存在递归调用self.get_descendant_leaves，get_children是无递归函数，用于计算节点的直接子节点（最多8个，通常为1-3个）。崩溃前多线程递归深度达到2-3k。

我知道可以手动改成循环+可变向量的方式修复，但想知道是否能通过调整flatten或collect的使用方式，让Rust自动避免栈空间增长？我猜想递归调用在闭包中可能延迟执行，编译器或许能自动展开。

调试工具咨询 #

我目前用println和lldb的thread backtrace排查问题，耗时很久，请问还有哪些工具或方法能高效诊断Rust栈溢出？

补充测试代码 #

以下是平行结构的调试代码，递归探索类斐波那契树并构建扁平化向量，请问能否保留递归定义的同时避免栈溢出？

fn main() {
    let awful = awful_vec_builder(10, 0);
    println!("See it's awful: {:?}", awful);
    println!("Let's smash the stack:");
    let more_awful = awful_vec_builder(5000, 0);
    println!("Please don't reach this case: {}", more_awful.len())
}

fn awful_vec_builder(i: usize, depth: usize) -> Vec<usize> {
    if i < 2 {
        vec![depth]
        //Note that using vec![] here still overflows the stack
    } else {
        let v = vec![i - 1, i - 2];
        v.iter()
            .map(|i| awful_vec_builder(*i, depth + 1))
            .flatten()
            .collect()
    }
}

解答 #

关于递归优化的可能性 #

首先，Rust编译器目前无法自动将这种树状递归转换为迭代逻辑。你的递归属于多分支递归（每个节点触发多个子递归调用），而Rust仅对单一尾调用场景有实验性的尾递归优化（TCO），且默认未启用稳定支持。代码中的递归调用在map闭包内，一旦flatten或collect触发迭代，每个子递归会立即执行并占用栈空间，直到叶子节点才开始返回，栈深度会随树的深度线性增长，调整flatten或collect无法改变这个本质。

要保留递归风格同时避免栈溢出，有两种可行方向：

1. 手动模拟递归栈：将递归状态（当前节点、待处理节点队列等）封装到堆上的结构体中，用循环处理状态，把调用栈的压力转移到堆内存。
2. 改用迭代式遍历：这是最直接高效的方案，手动维护栈或队列，遍历过程中直接收集叶子节点，完全规避调用栈溢出。

针对你的get_descendant_leaves，迭代版示例如下：

fn get_descendant_leaves(&self, p: Point) -> Vec<Point> {
    let mut leaves = Vec::new();
    let mut stack = vec![p];
    
    while let Some(node) = stack.pop() {
        let children = self.get_children(node);
        if children.is_empty() {
            leaves.push(node);
        } else {
            // 反向入栈保证遍历顺序和递归一致（可选）
            stack.extend(children.into_iter().rev().map(|c| c.0));
        }
    }
    
    leaves
}

针对补充的awful_vec_builder，迭代版实现：

fn awful_vec_builder(i: usize, depth: usize) -> Vec<usize> {
    let mut leaves = Vec::new();
    let mut stack = vec![(i, depth)];
    
    while let Some((current, d)) = stack.pop() {
        if current < 2 {
            leaves.push(d);
        } else {
            // 反向入栈保持和递归相同的遍历顺序
            stack.push((current - 2, d + 1));
            stack.push((current - 1, d + 1));
        }
    }
    
    leaves
}

栈溢出诊断工具与方法 #

除了println和lldb回溯，还有这些高效方式：

• RUST_BACKTRACE=1环境变量：运行程序时设置RUST_BACKTRACE=1 ./your_binary，程序崩溃时自动打印完整调用栈，无需手动启动调试器，快速定位溢出点和递归深度。
• rust-gdb/rust-lldb断点监控：在递归函数入口设断点，每次触发时用info stack（gdb）或bt（lldb）查看当前栈深度，配合watch命令监控栈指针变化，快速掌握栈增长规律。
• valgrind massif工具：分析内存（包括栈）使用情况，生成栈内存随时间变化的图表，直观看到溢出前的增长趋势。
• 编译器lint与警告：启用#![warn(unconditional_recursion)]提前排查无限递归；用clippy的recursion_limit lint，提示递归深度可能超出默认栈大小（Rust默认栈通常为8MB，2-3k深度的递归若每个栈帧占用几KB，极易超出）。
• 自定义栈深度监控：在递归函数中添加线程局部存储的深度计数器，超过阈值时panic并打印深度，快速确认溢出时的深度值，示例：

  use std::cell::Cell;
  thread_local! {
      static DEPTH: Cell<usize> = Cell::new(0);
  }
  
  fn get_descendant_leaves(&self, p: Point) -> Vec<Point> {
      DEPTH.with(|d| d.set(d.get() + 1));
      if DEPTH.with(|d| d.get()) > 2000 {
          panic!("Recursion depth exceeded: {}", DEPTH.with(|d| d.get()));
      }
      
      let result = {
          let children = self.get_children(p);
          if children.is_empty() {
              vec![p]
          } else {
              children
                  .iter()
                  .map(|child_p| self.get_descendant_leaves(child_p.0))
                  .flatten()
                  .collect()
          }
      };
      
      DEPTH.with(|d| d.set(d.get() - 1));
      result
  }
  

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