【kotlin】递归和尾递归

文章目录

• ​​递归​​
• ​​尾递归优化​​

递归

递归（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))      

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)
    }
}