递归

递归（Recursive）是指自己方法内部调用自己

我们来算一下5的阶乘

fun main(args: Array<String>) {
	//5的阶乘：5*4*3*2*1
	var num = 5
	println(fact(num))
}

fun fact(num:Int):Int{
	if(num == 1){
		return 1
	}else{
		return num*fact(num-1)
	}
}

我们来算一下100的阶乘

var num = 100
println(fact(num))

结果居然是

因为100的阶乘是一个远远超过Int范围的数，所以我们需要定义一个BigInteger

import java.math.BigInteger

fun main(args: Array<String>) {
	//5的阶乘：5*4*3*2*1
	var num = BigInteger("100")
	println(fact(num))
}

fun fact(num:BigInteger):BigInteger{
	if(num == BigInteger.ONE){
		return BigInteger.ONE
	}else{
		return num*fact(num-BigInteger.ONE)
	}
}

然后你就会得到一个把你吓尿的数…

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

尾递归优化

尾递归就是递归时只返回函数本身，没有其他计算

我们来算一下累加运算，先用普通的递归

fun main(args: Array<String>) {
	//5的累加：5+4+3+2+1
	var num = 5
	println(ollAdd(num))
}

fun ollAdd(num:Int):Int{
	if(num == 1){
		return 1
	}else{
		return num+ollAdd(num-1)
	}
}

现在我们来算一下100000的累加

	var num = 100000
	println(ollAdd(num))

运行程序，因为很消耗内存会报错，这是一个堆栈溢出的错误

在kotlin中，我们写成尾递归的时候，配合关键字 tailrec，修改程序如下：

fun main(args: Array<String>) {
	var result = 0
	println(ollAdd(5,result))
}

tailrec fun ollAdd(num:Int,result:Int):Int{
	if(num == 0){
		return result
	}else{
		return ollAdd(num-1,num+result)
	}
}

尾递归就是递归时只返回函数本身，没有其他计算。配合关键字 tailrec使用