Kotlin 遞歸和尾遞歸

在本文中，您將學(xué)習(xí)創(chuàng)建遞歸函數(shù)。一個(gè)自我調(diào)用的函數(shù)。此外，您還將了解尾遞歸函數(shù)。

調(diào)用自身的函數(shù)稱為遞歸函數(shù)。并且，這種技術(shù)稱為遞歸。

一個(gè)物理世界的實(shí)例是將兩個(gè)平行的鏡子相對(duì)放置。它們之間的任何對(duì)象都將被遞歸地反射。

遞歸在編程中如何工作？

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

fun recurse() {
    ... .. ...
    recurse()
    ... .. ...
}

在這里，從recurse()函數(shù)本身的主體中調(diào)用recurse()函數(shù)。 該程序的工作原理如下：

在這里，遞歸調(diào)用永遠(yuǎn)持續(xù)下去，從而導(dǎo)致無限遞歸。

為了避免無限遞歸，可以在一個(gè)分支進(jìn)行遞歸調(diào)用而其他分支不遞歸調(diào)用的情況下使用if ... else（或類似方法）。

示例：使用遞歸查找數(shù)字的階乘

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)
}

運(yùn)行該程序時(shí)，輸出為：

4 階乘 = 24

該程序如何工作？

factorial()下圖說明了該函數(shù)的遞歸調(diào)用：

涉及的步驟如下：

factorial(4)              // 第1次函數(shù)調(diào)用，參數(shù): 4
4*factorial(3)            // 第2次函數(shù)調(diào)用，參數(shù): 3
4*(3*factorial(2))        // 第3次函數(shù)調(diào)用，參數(shù): 2
4*(3*(2*factorial(1)))    // 第4次函數(shù)調(diào)用，參數(shù): 1 
4*(3*(2*1))                 
24

Kotlin 尾遞歸

尾遞歸不是Kotlin語言的特征，而是一個(gè)通用概念。 包括 Kotlin 在內(nèi)的一些編程語言使用它來優(yōu)化遞歸調(diào)用，而其他語言(例如 Python )不支持它們。

什么是尾遞歸？

在普通遞歸中，首先執(zhí)行所有遞歸調(diào)用，最后根據(jù)返回值計(jì)算結(jié)果（如上面的示例所示）。所以，在進(jìn)行所有遞歸調(diào)用之前，您不會(huì)得到結(jié)果。

在尾遞歸中，首先執(zhí)行計(jì)算，然后執(zhí)行遞歸調(diào)用(遞歸調(diào)用將當(dāng)前步驟的結(jié)果傳遞給下一個(gè)遞歸調(diào)用)。 這使得遞歸調(diào)用等同于循環(huán)，并避免了堆棧溢出的風(fēng)險(xiǎn)。

尾遞歸的條件

如果對(duì)自身的函數(shù)調(diào)用是它執(zhí)行的最后一個(gè)操作，則該遞歸函數(shù)可以進(jìn)行尾部遞歸。例如，

示例1：不符合尾部遞歸的條件，因?yàn)閷?duì)其自身的函數(shù)調(diào)用 n*factorial(n-1) 不是最后一個(gè)操作。

fun factorial(n: Int): Long {

    if (n == 1) {
        return n.toLong()
    } else {
        return n*factorial(n - 1)     
    }
}

示例2：符合尾遞歸條件，因?yàn)閷?duì)自身的函數(shù)調(diào)用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中執(zhí)行尾部遞歸，您需要使用tailrec修飾符標(biāo)記該函數(shù)。

示例：尾遞歸

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)
}

運(yùn)行該程序時(shí)，輸出為：

354224848179261915075

這個(gè)程序計(jì)算斐波納契級(jí)數(shù)的第100項(xiàng)。 因?yàn)檩敵隹梢允欠浅４蟮恼麛?shù)，所以我們從Java標(biāo)準(zhǔn)庫(kù)中導(dǎo)入了BigInteger類。

在這里，函數(shù)fibonacci()用trarec修飾符標(biāo)記，該函數(shù)有資格進(jìn)行尾遞歸調(diào)用。 因此，編譯器在這種情況下優(yōu)化了遞歸。

如果您試圖在不使用尾遞歸的情況下查找斐波納契數(shù)列的第20000項(xiàng)(或任何其他大整數(shù))，編譯器將拋出 java.lang.StackOverflowError 異常。
但是，我們上面的程序運(yùn)行得很好。 這是因?yàn)槲覀兪褂昧宋策f歸，它使用了高效的基于循環(huán)的版本，而不是傳統(tǒng)的遞歸。

示例：使用尾遞歸的階乘

上述示例（第一個(gè)示例）中用于計(jì)算數(shù)字階乘的示例無法針對(duì)尾遞歸進(jìn)行優(yōu)化。 這是執(zhí)行相同任務(wù)的另一個(gè)程序。

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)
}

運(yùn)行該程序時(shí)，輸出為：

5 階乘= 120

編譯器可以在該程序中優(yōu)化遞歸，因?yàn)檫f歸函數(shù)可以進(jìn)行尾遞歸，并且我們使用了tailrec修飾符，告訴編譯器優(yōu)化遞歸。