如何将基于Future的分页API递归调用改造为尾递归？

首先明确核心原因：你的递归调用是在Future.flatMap的回调函数内部执行的，这并不是当前函数的尾调用（尾调用要求递归是函数执行的最后一步，且无需保留当前函数栈帧）。由于flatMap会返回新的Future，递归调用属于异步回调逻辑，编译器无法将其识别为尾递归，因此无法添加@tailrec注解。

不过我们可以通过两种方式实现类似尾递归的效果（避免栈溢出），甚至写出能被@tailrec识别的代码。

方案一：累积参数+异步链式调用（最常用） #

这种方式不需要@tailrec注解，但依托异步回调的特性，不会出现栈溢出问题（每一次递归调用都在新的线程栈中执行，栈帧不会累积）。核心是用累积参数保存已获取的数据，递归时传递该参数。

示例代码：

import scala.concurrent.{Future, ExecutionContext}

// 定义分页数据结构
case class PageData(data: List[String], nextPageUrl: Option[String])

// 模拟分页API调用
def fetchPage(url: String)(implicit ec: ExecutionContext): Future[PageData] = Future {
  url match {
    case "page1" => PageData(List("data1", "data2"), Some("page2"))
    case "page2" => PageData(List("data3", "data4"), None)
    case _ => PageData(Nil, None)
  }
}

// 改造后的分页获取函数
def fetchAllPages(url: String)(implicit ec: ExecutionContext): Future[List[String]] = {
  // 辅助函数：接收累积数据和下一页URL，返回最终结果的Future
  def loop(acc: List[String], nextUrl: String): Future[List[String]] = {
    fetchPage(nextUrl).flatMap { page =>
      val newAcc = acc ++ page.data
      page.nextPageUrl match {
        // 没有下一页，返回累积的所有数据
        case None => Future.successful(newAcc)
        // 有下一页，递归调用loop，传递新的累积值和下一页URL
        case Some(url) => loop(newAcc, url)
      }
    }
  }

  // 初始调用：累积值为空，从第一页开始
  loop(Nil, url)
}

说明： #

• 虽然loop函数无法添加@tailrec，但异步回调的特性保证了栈帧不会在同一线程中累积，不会出现栈溢出。
• 若数据量较大，可将List替换为ListBuffer提升拼接性能。

方案二：同步尾递归+处理已完成的Future（可加@tailrec） #

如果一定要让函数能被@tailrec注解识别，可以编写同步尾递归函数，专门处理已完成的Future，未完成的Future则直接返回，等待异步完成后继续递归。

示例代码：

import scala.concurrent.{Future, ExecutionContext}
import scala.annotation.tailrec
import scala.util.Try

case class PageData(data: List[String], nextPageUrl: Option[String])

def fetchPage(url: String)(implicit ec: ExecutionContext): Future[PageData] = Future {
  url match {
    case "page1" => PageData(List("data1", "data2"), Some("page2"))
    case "page2" => PageData(List("data3", "data4"), None)
    case _ => PageData(Nil, None)
  }
}

def fetchAllPages(url: String)(implicit ec: ExecutionContext): Future[List[String]] = {
  // 尾递归辅助函数：接收当前的Future（包含累积数据和下一页URL）
  @tailrec
  def buildChain(current: Future[(List[String], Option[String])]): Future[(List[String], Option[String])] = {
    current.value match {
      // 如果Future已经完成，同步处理并递归
      case Some(Try((acc, nextUrl))) =>
        nextUrl match {
          case None => current
          case Some(url) =>
            val nextFuture = fetchPage(url).map(page => (acc ++ page.data, page.nextPageUrl))
            buildChain(nextFuture)
        }
      // 如果Future未完成，直接返回，等待异步完成后触发后续逻辑
      case None => current
    }
  }

  // 初始Future：获取第一页数据，包装成(累积数据, 下一页URL)的形式
  val initial = fetchPage(url).map(page => (page.data, page.nextPageUrl))
  // 构建链式调用后，取出累积的所有数据
  buildChain(initial).map(_._1)
}

说明： #

• buildChain是真正的尾递归函数，可添加@tailrec注解，编译器会对其进行栈优化。
• 函数会检查当前Future的状态：已完成则同步处理并递归，未完成则返回当前Future，等待异步完成后继续执行。

额外提示 #

如果分页数据量极大，或需要更优雅的异步流处理，可考虑使用Akka Streams或FS2这类流式处理库，它们天生支持分页数据的流式获取，无需手动编写递归，还能避免内存溢出问题。

内容的提问来源于stack exchange，提问作者M.G.