Scala如何编写递归Ad hoc函数实现双列表拼接且不使用内置concat

核心思路 #

Scala 标准库的List是不可变单向链表结构，我们可以基于链表的头、尾拆分特性做递归处理，全程仅使用List的基础构造操作，不调用任何内置拼接函数：

• 递归终止条件：左侧列表为空时，直接返回右侧列表即可完成拼接
• 递归迭代逻辑：每次取出左侧列表的头元素，拼接到「剩余左列表和右列表的递归拼接结果」的头部即可

基础递归实现 #

def concatList(lleft: List[String], lright: List[String]): List[String] = lleft match {
  case Nil => lright
  case head :: tail => head :: concatList(tail, lright)
}

注：这里用模式匹配做列表拆分更符合Scala函数式写法，如果你想用if判断也可以替换成：

def concatList(lleft: List[String], lright: List[String]): List[String] = {
  if (lleft.isEmpty) lright
  else lleft.head :: concatList(lleft.tail, lright)
}

实现说明 #

• 全程仅用到List的基础操作：空列表判断/匹配、取头元素head、取尾列表tail、链表构造操作::，没有使用++、concat等任何内置拼接功能
• 递归执行逻辑示例：输入concatList(List("a","b"), List("c","d"))
  1. 匹配到"a" :: List("b")，返回"a" :: concatList(List("b"), List("c","d"))
  2. 匹配到"b" :: Nil，返回"b" :: concatList(Nil, List("c","d"))
  3. 匹配到Nil直接返回List("c","d")
  4. 回溯拼接得到最终结果List("a","b","c","d")

大列表优化：尾递归版本 #

如果需要处理超长列表避免栈溢出，可以改写成尾递归实现，让编译器做尾递归优化：

import scala.annotation.tailrec

def concatList(lleft: List[String], lright: List[String]): List[String] = {
  @tailrec
  def loop(remainLeft: List[String], result: List[String]): List[String] = remainLeft match {
    case Nil => result
    case head :: tail => loop(tail, head :: result)
  }
  loop(lleft.reverse, lright)
}

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