Scala普通递归实现两个列表元素求和功能的问题求助

普通递归和你已经实现的尾递归核心差异是：尾递归会把中间计算结果通过累加器参数一层层往下传，最后终止时直接返回累加结果；而普通递归不需要携带累加器，会先拆分出子问题完成计算，再将当前步的结果和子问题的返回结果拼接得到最终解。

你现有定义的callRecursive方法里的n、outputList都是尾递归需要的累加相关参数，普通递归版本可以完全去掉这两个入参，实现逻辑如下：

def callRecursive(list1 : List[Int], list2 : List[Int]) : List[Int]  = {
  // 终止条件：两个列表都为空时返回空列表
  if(list1.isEmpty && list2.isEmpty) {
    List()
  } 
  // 情况1：两个列表都有值，当前位求和后拼接子问题结果
  else if(!list1.isEmpty && !list2.isEmpty) {
    (list1.head + list2.head) :: callRecursive(list1.tail, list2.tail)
  }
  // 情况2：只有list2有值，直接取list2当前位拼接子问题结果
  else if(list1.isEmpty) {
    list2.head :: callRecursive(list1, list2.tail)
  }
  // 情况3：只有list1有值，直接取list1当前位拼接子问题结果
  else {
    list1.head :: callRecursive(list1.tail, list2)
  }
}

• 这里用::（列表头插法）把当前步的计算结果，拼到递归处理剩余列表得到的子结果前面，最终得到的顺序和你原来尾递归版本的结果完全一致
• 如果你必须保留原有方法的入参定义（即保留n、outputList参数），可以用n作为当前处理的索引，终止条件为n等于两个列表的最大长度，每次递归时n+1，但这种写法本质还是带累加器的实现，不符合普通递归的常规写法。

普通递归没有尾递归优化，当输入列表长度过长时会出现栈溢出问题，生产环境优先使用你已经实现的尾递归版本。

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