如何用尾递归与非尾递归实现列表按索引模3拆分三个子列表？

递归索引递增的核心思路 #

递归中索引的递增不需要用var维护，直接**在递归调用时传递index+1**即可——把索引作为递归函数的参数，每次递归都传入更新后的值，这是函数式编程里处理递归状态的标准方式。

你的代码问题分析 #

1. 递归调用splitList时未递增索引，应该传index+1而非原index
2. 终止条件错误返回空列表，正确逻辑是返回累积的三个子列表
3. index +1只是表达式，不会修改参数值，Scala中参数不可变
4. 元素处理顺序颠倒，尾递归应先处理当前元素再递归传递更新后的状态

尾递归实现（编译器可优化为循环） #

import scala.annotation.tailrec

def divideTailRec(list: List[Int]): (List[Int], List[Int], List[Int]) = {
  @tailrec
  def split(remaining: List[Int], acc1: List[Int], acc2: List[Int], acc3: List[Int], index: Int): (List[Int], List[Int], List[Int]) = {
    remaining match {
      case Nil => (acc1, acc2, acc3)
      case head :: tail =>
        index % 3 match {
          case 1 => split(tail, acc1 :+ head, acc2, acc3, index + 1)
          case 2 => split(tail, acc1, acc2 :+ head, acc3, index + 1)
          case _ => split(tail, acc1, acc2, acc3 :+ head, index + 1)
        }
    }
  }
  split(list, Nil, Nil, Nil, 0) // 索引从0开始计数
}

// 测试示例
println(divideTailRec(List(0,11,22,33))) // 输出：(List(11), List(22), List(0, 33))

• 用@tailrec注解确保编译器做尾递归优化（避免栈溢出）
• 每次递归根据当前索引的模3结果，将头元素追加到对应累积列表
• 终止时直接返回累积的三个列表，严格保持原元素顺序

非尾递归实现（回溯式处理） #

def divideNonTailRec(list: List[Int]): (List[Int], List[Int], List[Int]) = {
  def split(remaining: List[Int], currentIndex: Int): (List[Int], List[Int], List[Int]) = {
    remaining match {
      case Nil => (Nil, Nil, Nil)
      case head :: tail =>
        // 先递归处理剩余元素，得到后续拆分结果
        val (acc1, acc2, acc3) = split(tail, currentIndex + 1)
        // 回溯时将当前元素插入对应子列表头部（保持顺序）
        currentIndex % 3 match {
          case 1 => (head :: acc1, acc2, acc3)
          case 2 => (acc1, head :: acc2, acc3)
          case _ => (acc1, acc2, head :: acc3)
        }
    }
  }
  split(list, 0)
}

// 测试示例
println(divideNonTailRec(List(0,11,22,33))) // 输出：(List(11), List(22), List(0, 33))

• 先递归到列表末尾，再回溯处理每个元素
• 用head :: acc而非acc :+ head，因为列表头部插入是O(1)操作，效率更高
• 同样通过递归调用传递currentIndex +1实现索引递增

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