Kotlin基础 - 第十二章尾递归优化

#### [kotlin官方文档 https://www.kotlincn.net/docs/reference/](https://www.kotlincn.net/docs/reference/) ####

函数递归必然会损失一定的函数性能，相对来说函数循环的效率就会相对高很多了，于是我们如果可以将我们的递归函数优化成循环调用，岂不是美滋滋，其实在某种情况下，Kotlin底层为我们实现了这种优化。

尾递归：在函数表达式前面增加关键字 `` 编译器会自动将递归函数优化编译成循环函数

递归函数求解菲波那切数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368…

这个数列从第3项开始，每一项都等于前两项之和。

通常我们可以使用递归函数求解：

	fun fbnq(n: Long, x: Long = 0, y: Long = 1): Long {
	    if (n === 0L) return x;
	    return fbnq(n - 1, y, x + y)
	}
	
	
	
	fun main(args: Array<String>) {
	    var timeStart = System.currentTimeMillis()
	    println("函数调用开始时间 ${timeStart}")
	    fbnq(1000).println()
	    var timeEnd = System.currentTimeMillis()
	    println("函数调用结束时间 ${timeEnd}")
	    print("累计用时 ${timeEnd - timeStart}")
	}

运行结果

	函数调用开始时间 1587185374640
	817770325994397771
	函数调用结束时间 1587185374642
	累计用时 2

调用这个函数，给的数值小一些，还没什么问题，像例子中求第100个斐波那契数列的值，就会久久的卡住不动，更大些还有可能造成堆栈溢出的错误。

尾递归的优化，函数怎加 tailrec 修饰

	tailrec fun fbnq(n: Long, x: Long = 0, y: Long = 1): Long {
	    if (n === 0L) return x;
	    return fbnq(n - 1, y, x + y)
	}
	
	
	
	fun main(args: Array<String>) {
	    var timeStart = System.currentTimeMillis()
	    println("函数调用开始时间 ${timeStart}")
	    fbnq(1000).println()
	    var timeEnd = System.currentTimeMillis()
	    println("函数调用结束时间 ${timeEnd}")
	    print("累计用时 ${timeEnd - timeStart}")
	}

运行结果

	函数调用开始时间 1587185479771
	817770325994397771
	函数调用结束时间 1587185479772
	累计用时 1

上面的写法就是使用尾调用优化的递归函数

尾调用(Tail Call)

尾调用的本身的概念非常简单，就是指某个函数的最后一步是调用另一个函数。

	fun f(x:String){
	  return g(x);
	}

• 以下三种情况均不属于尾调用

    // 情况一 调用函数之后还有赋值操作
    fun f(x:String){
      var y = g(x);
      return y;
    }
    
    // 情况二 调用函数之后 又进行了一步运算
    fun f(x:String){
      return g(x) + 1;
    }
    
    // 情况三 没有return 表示最后一步是 return undefined
    fun f(x:String){
      g(x);
    }
  

尾调用不一定要出现在函数尾部，只要是最后一步操作就可以。

	fun f(x) {
	  if (x > 0) {
	    return m(x)
	  }
	  return n(x);
	}

上述函数m和n都属于尾调用，因为他们都是函数f的最后一步操作。

注意尾递归调用需要满足两个条件

1. 函数必须是为尾调用函数

2. 函数必须使用关键字 tailrec修饰，编译器底层会对代码进行优化变成迭代，提高函数的执行效率和内存占用

注意： 对于非尾递归增加关键字 tailrec 编译器也是不会帮我们优化的

尾递归

函数调用自身，称为递归。如果尾调用自身，就称为尾递归。

递归非常耗费内存，因为需要同时保存成千上百个调用帧，很容易发生“栈溢出”错误（stack overflow）。但对于尾递归来说，由于只存在一个调用帧，所以永远不会发生“栈溢出”错误。

往往需要改写递归函数，确保最后一步只调用自身。做到这一点的方法，就是把所有用到的内部变量改写成函数的参数。