你好,游客 登录
背景:
阅读新闻

Scala面试题:什么是尾递归?

[日期:2018-09-15] 来源:jiansh  作者:IIGEOywq [字体: ]

正常递归,每一次递归步骤,需要保存信息到堆栈里面,当递归步骤很多时,导致堆栈溢出。
尾递归就是为了解决上述问题,在尾递归中所有的计算都是在递归之前调用,
编译器可以利用这个属性避免堆栈错误,尾递归的调用可以使信息不插入堆栈,从而优化尾递归。
使用 @tailrec 标签可使编译器强制使用尾递归。
代码示例:

def sum(n: Int): Int = { // 求和计算
  if(n == 0) {
    n
  } else {
    n + sum(n - 1)
  }
}

@tailrec  //告诉编译器
def tailSum(n: Int, acc: Int = 0): Int = {
  if(n == 0) {
    acc
  } else {
    tailSum(n - 1, acc + n)
  }
}

sum(5)
5 + sum(4) // 暂停计算 => 需要添加信息到堆栈
5 + (4 + sum(3))
5 + (4 + (3 + sum(2)))
5 + (4 + (3 + (2 + sum(1))))
5 + (4 + (3 + (2 + 1)))
15

tailSum(5) // tailSum(5, 0) 默认值是0
tailSum(4, 5) // 不需要暂停计算
tailSum(3, 9)
tailSum(2, 12)
tailSum(1, 14)
tailSum(0, 15)
15


作者:IIGEOywq
链接:https://www.jianshu.com/p/ace2bb24dc11
來源:简书
简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。
收藏 推荐 打印 | 阅读: