Kotlin - 尾递归优化

简介: Kotlin - 尾递归优化

本系列学习教程笔记属于详细讲解Kotlin语法的教程,需要快速学习Kotlin语法的小伙伴可以查看“简洁” 系列的教程

快速入门请阅读如下简洁教程:
Kotlin学习教程(一)
Kotlin学习教程(二)
Kotlin学习教程(三)
Kotlin学习教程(四)
Kotlin学习教程(五)
Kotlin学习教程(六)
Kotlin学习教程(七)
Kotlin学习教程(八)
Kotlin学习教程(九)
Kotlin学习教程(十)

Kotlin教程笔记(24) -尾递归优化

imgKotlin - 尾递归优化

#尾递归

尾递归就是函数在调用完自己之后没有其他操作的递归,是递归的一种特殊形式。举个例子,"计算斐波那契数列第 n 项"的递归算法有哪些?

#简单递归实现

斐波那契数列第 0、1 位都是 1,从第二位开始,每项是前两位之和,因此用递归算法很容易就能实现出来了:

fun fib1(n: Int): Int {
    if (n == 0 || n == 1) return 1
    return fib1(n - 1) + fib1(n - 2);
}

这种写法虽然递归调用是在方法的最后一行,但其实这里还有结果相加的操作,并不符合尾递归的定义。

简单递归虽然容易理解,但实际上,该算法会有冗余计算,比如:fib1(2)会被执行多次,如果 n 越大,这种冗余计算就会越多:

image-20241015093649384

#尾递归实现

为了解决上述简单递归实现的弊端,我们可以把已经计算过的结果保存起来,传递给下次计算,所以可以将递归写法进行优化:

fun fib2(n: Int): Int {
    return fibIter(1, 1, n);
}

fun fibIter(a: Int, b: Int, n: Int): Int {
    // return if (n == 0) a else fibIter(b, a + b, n - 1) // 简便写法
    if (n == 0) {
        return a
    } else {
        return fibIter(b, a + b, n - 1)
    }
}

其中,fibIter() 的递归代码在方法的最后一行,调用完也没有其他的操作,符合尾递归的定义。

#性能对比

理论归理论,我们还是得用实际代码来测试一下两种递归算法的运行耗时情况,这种才更能直观看出差别,为了方便测试,这里写了一个耗时测试方法:

fun timeConsume(operation: () -> Unit) {
    val begin = System.currentTimeMillis()
    operation()
    val end = System.currentTimeMillis()
    println("begin = ${begin}ms , end = ${end}ms , 耗时 ${end - begin}ms")
}

分别将两种递归算法丢到耗时测试方法 timeConsume() 中,得到测试结果:

fun main(args: Array<String>) {
    timeConsume {
        println(fib1(45))
    }
    // 1836311903
    // begin = 1612368480299ms , end = 1612368486217ms , 耗时 5918ms

    timeConsume {
        println(fib2(45))
    }
    // 1836311903
    // begin = 1612368486217ms , end = 1612368486217ms , 耗时 0ms
}

为了拿到斐波那契数列第 45 个元素值,fib1() 耗时近 6s,而 fib2() 耗时 0ms,这是何等的差距。

注意:测试 fib1(50) 会内存溢出。

#尾递归优化(tailrec)

虽然上述尾递归算法的耗时很小,但我们知道,递归算法效率其实并不高,因为每递归一次就要开辟一个方法栈,这是有性能消耗的,还有可能因为递归次数过多导致出现内存溢出的情况,而迭代算法就没有这种问题:

fun fib3(n: Int): Int {
    if (n == 0 || n == 1) return 1
    var a = 1
    var b = 1
    for (i in 0 until n) {
        val a_ = b
        val b_ = a + b
        a = a_
        b = b_
    }
    return a
}

同样的,我们来对尾递归算法和迭代算法进行耗时测试:

fun main(args: Array<String>) {
    timeConsume {
        println(fib2(12000))
    }
    // 690383169
    // begin = 1612369032575ms , end = 1612369032578ms , 耗时 3ms

    timeConsume {
        println(fib3(12000))
    }
    // 690383169
    // begin = 1612369032578ms , end = 1612369032579ms , 耗时 1ms
}

理论与实际相结合,通过测试结果可以得知,尾递归算法和迭代算法的差距还是有的,如果电脑 CPU 性能较低,或者方法中存在内存操作,这个差距会更大。

注意:因为"计算斐波那契数列第 n 项"这个算法题目仅仅只是数值运行,对于这 2 个算法来说太 easy 了,都是毫秒级别的,所以,需要取较后的元素这样计算量会多一点才能看出差距,同时因为递归过多会出现内存溢出,因此 n 的取值也不能太大,测试 15000 会内存溢出,12000 则不会。

既然递归有这种缺点,那么我们以后就杜绝使用递归算法吧?当然不行,递归也有一个很大的优点,那就是代码逻辑理解容易,既然这样,那有没有办法让递归算法的性能跟迭代算法一样呢?还真有,Kotlin 提供了 tailrec 关键字,可以让 尾递归算法 在编译期自动进行代码优化,从而解决尾递归算法的缺点。我们将 fibIter() 加上 tailrec 关键字:

fun fib2(n: Int): Int {
    return fibIter(1, 1, n);
}

// 只加了 tailrec 关键字
tailrec fun fibIter(a: Int, b: Int, n: Int): Int {
    return if (n == 0) a else fibIter(b, a + b, n - 1)
}

再来测试 fib2() 与 fib3() 两个算法的耗时情况:

fun main(args: Array<String>) {
    timeConsume {
        println(fib2(50000))
    }
    // -1256600222
    // begin = 1612370134450ms , end = 1612370134451ms , 耗时 1ms

    timeConsume {
        println(fib3(50000))
    }
    // -1256600222
    // begin = 1612370134452ms , end = 1612370134453ms , 耗时 1ms
}

这原本传入 15000 就会出现内存溢出的尾递归算法 fib2(),现在居然能传入 50000 了,耗时也与迭代算法 fib3() 一样,这就是 tailrec 关键字的厉害之处。

注意:tailrec 关键字只能优化尾递归算法,其它递归算法无法优化。

相关文章
|
17天前
|
算法 Kotlin
Kotlin教程笔记(24) -尾递归优化
Kotlin教程笔记(24) -尾递归优化
Kotlin教程笔记(24) -尾递归优化
|
10天前
|
算法 Kotlin
Kotlin教程笔记(24) -尾递归优化
Kotlin教程笔记(24) -尾递归优化
22 5
Kotlin教程笔记(24) -尾递归优化
|
13天前
|
算法 Kotlin
Kotlin教程笔记(24) -尾递归优化
Kotlin教程笔记(24) -尾递归优化
25 6
Kotlin教程笔记(24) -尾递归优化
|
24天前
|
调度 Android开发 开发者
构建高效Android应用:探究Kotlin多线程优化策略
【10月更文挑战第11天】本文探讨了如何在Kotlin中实现高效的多线程方案,特别是在Android应用开发中。通过介绍Kotlin协程的基础知识、异步数据加载的实际案例,以及合理使用不同调度器的方法,帮助开发者提升应用性能和用户体验。
40 4
|
29天前
|
算法 Kotlin
Kotlin教程笔记(24) -尾递归优化
Kotlin教程笔记(24) -尾递归优化
32 6
|
30天前
|
算法 Kotlin
Kotlin教程笔记(24) -尾递归优化
Kotlin教程笔记(24) -尾递归优化
|
3月前
|
前端开发 编译器 测试技术
Kotlin Multiplatform 跨平台开发的优化策略与实践
本文深入讲解Kotlin Multiplatform(KMP)的优化策略与实践。KMP是由JetBrains推出的开源技术,允许跨平台共享代码同时保持原生优势。文章覆盖KMP核心概念、性能优化技巧(如代码结构优化、利用`expect`/`actual`关键字、Kotlin/Native性能特性等),以及在移动、桌面和Web应用的实际案例分析。此外,还介绍了如何利用KMP生态系统工具进行快速开发,并展望了KMP的未来发展。
64 0
|
3月前
|
Java 网络安全 UED
运用 Kotlin 语言,优化局域网管控软件
在数字化时代,Kotlin语言以其简洁高效的特性,成为优化局域网管控软件的新选择。Kotlin不仅与Java高度兼容,还引入扩展函数等新特性,使代码更精炼易读。通过简洁的语法和强大的函数式编程支持,Kotlin能有效提升开发效率及软件性能。例如,简单的网络连接检测与设备扫描功能即可轻松实现。此外,Kotlin的协程支持让异步编程更为高效,进一步提高了软件响应速度和用户体验。随着Kotlin的发展,其在局域网管控领域的应用将愈发广泛。
26 0
|
3月前
|
编译器 Android开发 开发者
Android经典实战之Kotlin 2.0 迁移指南:全方位优化与新特性解析
本文首发于公众号“AntDream”。Kotlin 2.0 已经到来,带来了 K2 编译器、多平台项目支持、智能转换等重大改进。本文提供全面迁移指南,涵盖编译器升级、多平台配置、Jetpack Compose 整合、性能优化等多个方面,帮助开发者顺利过渡到 Kotlin 2.0,开启高效开发新时代。
150 0
|
25天前
|
JSON 调度 数据库
Android面试之5个Kotlin深度面试题:协程、密封类和高阶函数
本文首发于公众号“AntDream”,欢迎微信搜索“AntDream”或扫描文章底部二维码关注,和我一起每天进步一点点。文章详细解析了Kotlin中的协程、扩展函数、高阶函数、密封类及`inline`和`reified`关键字在Android开发中的应用,帮助读者更好地理解和使用这些特性。
17 1