LeetCode买卖股票问题：Array与List递归性能差异原因探究

我在解决LeetCode的「买卖股票的最佳时机」问题时，采用了两种递归实现方案，性能差异显著，具体如下：

方案1：将Array转换为List后递归处理 #

def maxProfit(prices: Array[Int]): Int = {
  @tailrec
  def maxProfitHelp(prices: List[Int], maxProfit: Int, lastBuy: Int): Int = {
    prices match {
      case Nil => maxProfit
      case head :: tail => if (head > lastBuy)  {
        maxProfitHelp(tail, Math.max(maxProfit, head - lastBuy), lastBuy)
      } else {
        maxProfitHelp(tail, maxProfit, head)
      }
    }
  }

  val listPrices = prices.toList
  maxProfitHelp(listPrices.tail, 0, listPrices.head)
}

该方案耗时962ms，内存占用71.70MB。

方案2：直接对原始Array进行递归处理 #

def maxProfitWithoutList(prices: Array[Int]): Int = {
  @tailrec
  def maxProfitHelp(prices: Array[Int], maxProfit: Int, lastBuy: Int): Int = {
    prices match {
      case c if c.isEmpty => maxProfit
      case c => if (c.head > lastBuy)  {
        maxProfitHelp(c.tail, Math.max(maxProfit, c.head - lastBuy), lastBuy)
      } else {
        maxProfitHelp(c.tail, maxProfit, c.head)
      }
    }
  }

  maxProfitHelp(prices.tail, 0, prices.head)
}

该方案耗时9134ms，内存占用75.47MB。

可见Array递归的性能比List递归差10倍！请问造成这种差异的原因是什么？

问题解答 #

核心原因在于Scala中List和Array的底层结构以及tail操作的实现逻辑完全不同：

• List的特性：
  Scala的List是不可变单向链表，每个节点仅保存当前元素和下一个节点的引用。调用tail时只是返回下一个节点的引用，无元素复制或内存分配，操作复杂度为O(1)；同时head :: tail的模式匹配是编译器优化后的高效操作，几乎无额外开销。尾递归过程中每一步都只是传递引用，整体时间复杂度为O(n)。

• Array的特性：
  Scala的Array本质是JVM原生连续内存数组。调用tail方法时会创建一个新数组，复制原数组从索引1开始的所有元素，操作复杂度为O(n)。递归时每次调用tail都会复制剩余元素，总复制次数为n+(n-1)+...+1 = n(n+1)/2，实际时间复杂度为O(n²)；加上Array的模式匹配无法像List那样优化，每次匹配和tail操作都涉及新对象创建，进一步放大了性能和内存开销。

即便两个方法都用@tailrec实现了尾递归优化，Array版本的tail操作带来的O(n)复制开销无法消除，这就是两者性能差距悬殊的根本原因。

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