Kotlin尾遞歸優化

一、尾遞歸優化

1.遞歸的一種特殊形式

2.調用自身後無其他的操作

3.tailrec關鍵字提示編譯器尾遞歸優化

二、具體的來看看一下代碼說明

package net.println.kotlin.chapter5.tailrecursive

/**
 * @author:wangdong
 * @description:
 */

/**定義一個節點的list的集合*/
data class ListNode(var value: Int, var next: ListNode ?= null)

/**定義一個查找節點的方法*/
/**
 * 簡單的尾遞歸
 * head可能為空
 * ListNode可能為空
 * 對尾遞歸做優化，隻需要加一個關鍵字tailrec
 */
tailrec fun findListNode(head: ListNode ?,value: Int):ListNode ?{
    //如果傳進來的head為空，傳回空
    head ?: return null
    //如果找到head,就傳回head
    if (head.value == value) return head
    //如果沒有找到,遞歸繼續找，在調用了自身之後，沒有任何操作，直接傳回
    return findListNode(head.next,value)
}

/**階乘*/
fun factorial(n: Long):Long{
    //調用完之後，還進行了乘法，那麼這個就不是尾遞歸了
    return n * factorial(n - 1)
}

/**定義一個樹的節點*/
data class TreeNode(val value: Int){
    var left: TreeNode ?= null
    var right: TreeNode ?= null
}

/**定義一個查找的方法*/
/**
 * 傳入一個根節點root
 * 傳入要查找的值value
 * 傳回查找到的節點
 */
fun findTreeNode(root: TreeNode ?, value: Int):TreeNode?{
    root ?: return null
    if (root.value == value) return root
    //這邊調用了自己過後，又調用了一下自己，是以就不算是尾遞歸了
    return findTreeNode(root.left,value) ?: return findTreeNode(root.right,value)
}

fun main(args: Array<String>) {
    //遞歸節點數
    val MAX_NODE_COUNT = 100000
    //頭部節點所在的位置
    val head = ListNode(0)
    var p = head
    //寫一個for循環
    for (i in 1..MAX_NODE_COUNT){
        p.next = ListNode(i)
        p = p.next!!
    }
    //查找倒數第二個節點，找到了就把它的值打出來
    println(findListNode(head,MAX_NODE_COUNT - 2) ?.value)   //8
}           

好啦，結束啦