Scala中递归转尾递归：func1与test函数改造疑问

嘿，我来帮你搞定这两个问题！先从func1的双重调用拆分说起，再看test函数的尾递归转换~

你原来的func1之所以不是尾递归，是因为它最后一步是加法操作（func1(n/10) + func2(n%10)），而不是直接调用自身。尾递归要求函数的最后一步必须是递归调用，不能有后续的计算。

解决思路很简单：引入一个**累加器（accumulator）**来保存中间的阶乘和结果，把原本在递归返回后做的加法，提前到递归调用前完成。这样每一步递归的最后都是直接调用自身，满足尾递归条件。

改写后的func1代码如下：

import scala.annotation.tailrec

object TailRec {
  // 尾递归版本的func1
  def func1(n: Int): Int = {
    @tailrec
    def _func1(remaining: Int, accumulator: Int): Int = {
      if (remaining < 10) {
        // 剩下的数字不足两位，直接加上它的阶乘结果返回
        accumulator + func2(remaining)
      } else {
        // 取出当前最后一位的阶乘，加到累加器，递归处理高位数字
        val currentDigitFactorial = func2(remaining % 10)
        _func1(remaining / 10, accumulator + currentDigitFactorial)
      }
    }
    // 初始调用：从原数n开始，累加器初始为0
    _func1(n, 0)
  }

  // 你已经实现好的尾递归func2，保持不变
  def func2(n: Int): Int = {
    @tailrec
    def _func2(n: Int, result: Int): Int = {
      if (n <= 1) result
      else _func2(n - 1, n * result)
    }
    _func2(n, 1)
  }

  // 接下来处理test函数...
}

先澄清一下：你原来的test函数本身没有递归调用自身，所以严格来说不需要尾递归转换。但如果想让test的核心逻辑（计算各位阶乘和 + 和原数比较）更高效，可以把这两个步骤合并到一个尾递归辅助函数里，避免两次遍历数字的各位。

改写后的test函数如下：

def test(n: Int): Boolean = {
  if (n <= 2) false
  else {
    @tailrec
    def _test(remaining: Int, originalNum: Int, accumulator: Int): Boolean = {
      if (remaining < 10) {
        // 计算最后一位的阶乘，累加后和原数比较
        val totalFactorialSum = accumulator + func2(remaining)
        totalFactorialSum == originalNum
      } else {
        val currentDigitFactorial = func2(remaining % 10)
        _test(remaining / 10, originalNum, accumulator + currentDigitFactorial)
      }
    }
    // 初始调用：从原数n开始，传入原数用于比较，累加器初始为0
    _test(n, n, 0)
  }
}

这个版本的test把“计算阶乘和”与“比较”的逻辑合并到了同一个尾递归函数里，只需要遍历一次数字的各位，比原实现（先调用func1遍历一次，再比较）更高效，而且完全是尾递归的实现方式。

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