时间戳

首页 > 解决方案 > 如何将递归函数转换为尾递归版本？

scala - 如何将递归函数转换为尾递归版本？

问题描述

我有一个似乎无法使尾递归的函数。

我尝试使用额外的累加器创建辅助函数，但要么算法没有产生预期的结果，要么它真的不是尾递归的。

这是功能：

    def game(boardState: BoardState,
             pieces: List[ChessPiece],
             acc: Set[BoardState]): Set[BoardState] = pieces match {
      case Nil => acc + boardState // No more pieces, boardState solved
      case x :: xs => getStates(boardState, x, xs, acc)
    }

    def getStates(boardState: BoardState,
                  piece: ChessPiece,
                  rest: List[ChessPiece],
                  acc: Set[BoardState]): Set[BoardState] = {
      // Ask if there are available squares
      if (boardState.availableSquares.nonEmpty) {
          // Get the states from every available square
        boardState.availableSquares.foldLeft(Set[BoardState]())((innerAcc, sqr) => {
          // Get the next chess piece
          val nextPiece = buildPiece(piece, sqr)
          // Check if placing the piece would result in an existing piece being attacked
          if (boardState.withPieces.forall(sqr => !nextPiece.isAttacking(sqr))) {
            // Do the recursion with the new Board State
            val newState = boardState.placePiece(nextPiece)
            innerAcc ++ game(newState, rest, acc) //This is the part that is not tail recursive
          } else innerAcc
        })
      } else {
      // There are no available places, search ends here
        acc
      }
    }

提前感谢您的建议！

标签： scalarecursion

解决方案

嗯，game()电话getStates()和getStates()电话game()。这看起来像是蹦床可以处理的东西。

这是使用标准库中的 TailCalls的尝试。

import scala.util.control.TailCalls._

def game(boardState: BoardState,
         pieces: List[ChessPiece],
         acc: Set[BoardState]): TailRec[Set[BoardState]] = pieces match {
  case Nil => done(acc + boardState) // No more pieces, boardState solved
  case x :: xs => tailcall(getStates(boardState, x, xs, acc))
}

def getStates(boardState: BoardState,
              piece: ChessPiece,
              rest: List[ChessPiece],
              acc: Set[BoardState]): TailRec[Set[BoardState]] = done{
  // Ask if there are available squares
  if (boardState.availableSquares.nonEmpty) {
    // Get the states from every available square
    boardState.availableSquares.foldLeft(Set[BoardState]())((innerAcc, sqr) => {
      // Get the next chess piece
      val nextPiece = buildPiece(piece, sqr)
      // Check if placing the piece would result in an existing piece being attacked
      if (boardState.withPieces.forall(sqr => !nextPiece.isAttacking(sqr))) {
        // Do the recursion with the new Board State
        val newState = boardState.placePiece(nextPiece)
        innerAcc ++ tailcall(game(newState, rest, acc)).result
      } else innerAcc
    })
  } else {
    // There are no available places, search ends here
    acc
  }
}

警告：我在模拟所有缺失的部分（ , 等）后编译了它BoardState，ChessPiece所以我实际上并没有尝试运行它。下次请发布足够的代码，使其成为最小、完整、可验证的示例。

推荐阅读