7.尾递归优化

尾递归:最后一行调用自身之后没有任何操作直接返回
kotlin尾递归优化,关键字tailrec
如:

data class ListNode(val value: Int, var next: ListNode? = null)
 
fun findListNode(head: ListNode?, value: Int): ListNode?{
    head?: return  null
    if(head.value == value) return head
    return findListNode(head.next, value)
}

不优化的话大量的递归调用会报错stackoverflowError

fun main() {
    val MAX_NODE_COUNT = 100000
    val head = ListNode(0)
    var p = head
    for(i in 1.. MAX_NODE_COUNT){
        p.next = ListNode(i)
        p = p.next!!
    }
    println(findListNode(head, MAX_NODE_COUNT - 2)?.value)
}

//报错如下
Exception in thread "main" java.lang.StackOverflowError
优化后

tailrec fun findListNode(head: ListNode?, value: Int): ListNode?{
    head?: return  null
    if(head.value == value) return head
    return findListNode(head.next, value)
}

fun main() {
    val MAX_NODE_COUNT = 100000
    val head = ListNode(0)
    var p = head
    for(i in 1.. MAX_NODE_COUNT){
        p.next = ListNode(i)
        p = p.next!!
    }
    println(findListNode(head, MAX_NODE_COUNT - 2)?.value)
    //打印得到99998
}