Kotlin尾递归优化

墨蓝 2022-05-28 09:16 203阅读 0赞

一、尾递归优化  
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
    }

好啦，结束啦