尾递归

// 尾递归

// 一般的递归

// 一个从 0 累加到 n 的函数

func sum(_ n: UInt) -> UInt{
  if n == 0 {
    return 0  
  }
  return n + sum(n - 1)
}

// 但是这里会出现错误，因为每次对于 sum 的递归调用都需要在调用栈上保存当前的状态，否则我们就无法计算最后的 n + sum(n -1) 当 n 足够大，调用栈足够深的时候，栈空间将被耗尽而导致错误，也就是栈溢出

// let = sum(1000000)

// 解决办法， 尾递归。 就是让函数里的最后一个动作是函数调用的形式，这个调用的返回值将直接被当前函数返回，而避免在栈上保存状态，这样以来程序就可以更新最后的栈帧，而不是新建一个，来避免栈溢出的发生。

func tailSum(_ n: UInt) -> UInt {
  func sumInternal(_ n: UInt, current: UInt) -> UInt{
      if n == 0{
      return current
      } else {
      return sumInternal(n - 1, current: current + n)
    }
  }
  return sumInternal(n, current: 0)
}

//let a = tailSum(100000)

//print(a)

// 这个尾递归在 Debu 模式下还是会报错，因为 Debug 模式下，Swift编译器不会对尾递归优化， Run 配置为 Release 就可以运行了