本文共 2902 字，大约阅读时间需要 9 分钟。

啥是尾递归

• 递归的一种形式
• 调用子身后无其他操作
• tailrec关键字提示编译器尾递归优化
• 尾递归与迭代的关系  tailrec就是让递归变成了迭代

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

看下 案列

package com.yzdzy.kotlin.chapter5import java.io.BufferedReaderimport java.io.FileReaderdata class ListNode(val value: Int, var next: ListNode?)//尾递归  就是函数调用自己之后直接返回 没有任何操作// 寻找链表头fun findListNode(head: ListNode?, value: Int): ListNode? {    head ?: return null    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}//非尾递归fun findTreeNode(root:TreeNode?,value: Int):TreeNode?{    root?:return null    if(root.value==null) return root    return findTreeNode(root.left,value)?:return findTreeNode(root.right,value)}

加上main案例测试下

package com.yzdzy.kotlin.chapter5import java.io.BufferedReaderimport java.io.FileReaderdata 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)}fun main(args: Array
   
    ) {    val MAX_NODE_COUNT = 10    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)}
   

1w个元素呢

package com.yzdzy.kotlin.chapter5import java.io.BufferedReaderimport java.io.FileReaderdata 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)}fun main(args: Array
   
    ) {    val MAX_NODE_COUNT = 10000    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 执行

package com.yzdzy.kotlin.chapter5import java.io.BufferedReaderimport java.io.FileReaderdata class ListNode(val value: Int, var next: ListNode? = null)//尾递归  就是函数调用自己之后直接返回 没有任何操作// 寻找链表头tailrec  fun findListNode(head: ListNode?, value: Int): ListNode? {    head ?: return null    if (head.value == value) return head    return findListNode(head.next, value)}fun main(args: Array
   
    ) {    val MAX_NODE_COUNT = 10000    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)}
   

9998