炫意html5
最早CSS3和HTML5移动技术网站之一

Kotlin 函数 – Kotlin 递归和尾递归

在本文中,您将学习创建递归函数。一个自我调用的函数。此外,您还将了解尾递归函数。

调用自身的函数称为递归函数。并且,这种技术称为递归。

一个物理世界的实例是将两个平行的镜子相对放置。它们之间的任何对象都将被递归地反射。

递归在编程中如何工作?

fun main(args: Array<String>) {
    ... .. ...
    recurse()
    ... .. ...
}
fun recurse() {
    ... .. ...
    recurse()
    ... .. ...
}

在这里,从recurse()函数本身的主体中调用recurse()函数。 该程序的工作原理如下:

Kotlin中的递归函数调用

在这里,递归调用永远持续下去,从而导致无限递归。

为了避免无限递归,可以在一个分支进行递归调用而其他分支不递归调用的情况下使用if … else(或类似方法)。

示例:使用递归查找数字的阶乘

fun main(args: Array<String>) {
    val number = 4
    val result: Long
    result = factorial(number)
    println("$number 阶乘 = $result")
}
fun factorial(n: Int): Long {
    return if (n == 1) n.toLong() else n*factorial(n-1)
}

运行该程序时,输出为:

4 阶乘 = 24

该程序如何工作?

factorial()下图说明了该函数的递归调用:

递归在Kotlin中如何工作?

涉及的步骤如下:

factorial(4)              // 第1次函数调用,参数: 4
4*factorial(3)            // 第2次函数调用,参数: 3
4*(3*factorial(2))        // 第3次函数调用,参数: 2
4*(3*(2*factorial(1)))    // 第4次函数调用,参数: 1 
4*(3*(2*1))                 
24

Kotlin 尾递归

尾递归不是Kotlin语言的特征,而是一个通用概念。 包括 Kotlin 在内的一些编程语言使用它来优化递归调用,而其他语言(例如 Python )不支持它们。

什么是尾递归?

在普通递归中,首先执行所有递归调用,最后根据返回值计算结果(如上面的示例所示)。所以,在进行所有递归调用之前,您不会得到结果。

在尾递归中,首先执行计算,然后执行递归调用(递归调用将当前步骤的结果传递给下一个递归调用)。 这使得递归调用等同于循环,并避免了堆栈溢出的风险。

尾递归的条件

如果对自身的函数调用是它执行的最后一个操作,则该递归函数可以进行尾部递归。例如,

示例1:不符合尾部递归的条件,因为对其自身的函数调用 n*factorial(n-1) 不是最后一个操作。

fun factorial(n: Int): Long {
    if (n == 1) {
        return n.toLong()
    } else {
        return n*factorial(n - 1)     
    }
}

示例2:符合尾递归条件,因为对自身的函数调用fibonacci(n-1, a+b, a)是最后的操作。

fun fibonacci(n: Int, a: Long, b: Long): Long {
    return if (n == 0) b else fibonacci(n-1, a+b, a)
}

要告诉编译器在Kotlin中执行尾部递归,您需要使用tailrec修饰符标记该函数。

示例:尾递归

import java.math.BigInteger
fun main(args: Array<String>) {
    val n = 100
    val first = BigInteger("0")
    val second = BigInteger("1")
    println(fibonacci(n, first, second))
}
tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger {
    return if (n == 0) a else fibonacci(n-1, b, a+b)
}

运行该程序时,输出为:

354224848179261915075

这个程序计算斐波纳契级数的第100项。 因为输出可以是非常大的整数,所以我们从Java标准库中导入了BigInteger类。

在这里,函数fibonacci()用trarec修饰符标记,该函数有资格进行尾递归调用。 因此,编译器在这种情况下优化了递归。

如果您试图在不使用尾递归的情况下查找斐波纳契数列的第20000项(或任何其他大整数),编译器将抛出 java.lang.StackOverflowError 异常。
但是,我们上面的程序运行得很好。 这是因为我们使用了尾递归,它使用了高效的基于循环的版本,而不是传统的递归。

示例:使用尾递归的阶乘

上述示例(第一个示例)中用于计算数字阶乘的示例无法针对尾递归进行优化。 这是执行相同任务的另一个程序。

fun main(args: Array<String>) {
    val number = 5
    println("$number 阶乘 = ${factorial(number)}")
}
tailrec fun factorial(n: Int, run: Int = 1): Long {
    return if (n == 1) run.toLong() else factorial(n-1, run*n)
}

运行该程序时,输出为:

5 阶乘= 120

编译器可以在该程序中优化递归,因为递归函数可以进行尾递归,并且我们使用了tailrec修饰符,告诉编译器优化递归。

炫意HTML5 » Kotlin 函数 – Kotlin 递归和尾递归

Java基础教程Android基础教程