# Kotlin 遞歸（遞歸函數）和尾遞歸 > 原文： [https://www.programiz.com/kotlin-programming/recursion](https://www.programiz.com/kotlin-programming/recursion) #### 在本文中，您將學習創建遞歸函數。 一個自我調用的函數。 此外，您還將了解尾遞歸函數。 調用自身的[函數](/kotlin-programming/functions)被稱為遞歸函數。 并且，這種技術稱為遞歸。 一個物理世界的例子是放置兩個相互面對的平行反射鏡。 它們之間的任何對象都將遞歸地反映出來。 * * * ### 遞歸在編程中如何工作？ ```kt fun main(args: Array<String>) { ... .. ... recurse() ... .. ... } fun recurse() { ... .. ... recurse() ... .. ... } ``` 在此，從`recurse()`函數本身的主體調用`recurse()`函數。 該程序的工作原理如下：  在這里，遞歸調用將永遠持續下去，從而導致無限遞歸。 為了避免無限遞歸，可以在一個分支進行遞歸調用而另一分支不遞歸的情況下使用 [if...else](/kotlin-programming/if-expression "C++ if...else") （或類似方法）。 * * * ### 示例：使用遞歸查找數字的階乘 ```kt fun main(args: Array<String>) { val number = 4 val result: Long result = factorial(number) println("Factorial of $number = $result") } fun factorial(n: Int): Long { return if (n == 1) n.toLong() else n*factorial(n-1) } ``` 運行該程序時，輸出為： ```kt Factorial of 4 = 24 ``` * * * ### 該程序如何工作？ 下圖說明了`factorial()`函數的遞歸調用：  涉及的步驟如下： ```kt factorial(4) // 1st function call. Argument: 4 4*factorial(3) // 2nd function call. Argument: 3 4*(3*factorial(2)) // 3rd function call. Argument: 2 4*(3*(2*factorial(1))) // 4th function call. Argument: 1 4*(3*(2*1)) 24 ``` * * * ### Kotlin 尾遞歸 尾遞歸是一個通用概念，而不是 Kotlin 語言的功能。 包括 Kotlin 在內的某些編程語言使用它來優化遞歸調用，而其他語言（例如 Python）不支持它們。 * * * ### 什么是尾遞歸？ 在普通遞歸中，首先執行所有遞歸調用，最后從返回值計算結果（如上例所示）。 因此，在進行所有遞歸調用之前，您不會得到結果。 在尾部遞歸中，首先執行計算，然后執行遞歸調用（遞歸調用將當前步驟的結果傳遞到下一個遞歸調用）。 這使得遞歸調用等效于循環，并避免了棧溢出的風險。 * * * ### 尾遞歸的條件 如果對自身的函數調用是它執行的最后一個操作，則該遞歸函數可以進行尾部遞歸。 例如， **示例 1**：不適合進行尾遞歸，因為對自身`n*factorial(n-1)`的函數調用不是最后的操作。 ```kt fun factorial(n: Int): Long { if (n == 1) { return n.toLong() } else { return n*factorial(n - 1) } } ``` **示例 2**：有資格進行尾遞歸，因為對自身`fibonacci(n-1, a+b, a)`的函數調用是最后的操作。 ```kt fun fibonacci(n: Int, a: Long, b: Long): Long { return if (n == 0) b else fibonacci(n-1, a+b, a) } ``` * * * 要告訴編譯器在 Kotlin 中執行尾部遞歸，您需要使用`tailrec`修飾符標記該函數。 * * * ### 示例：尾遞歸 ```kt 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) } ``` 運行該程序時，輸出為： ```kt 354224848179261915075 ``` 該程序計算斐波那契數列的第 100 項。 由于輸出可能是非常大的整數，因此我們從 Java 標準庫中導入了 [BigInteger](https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html) 類。 此處，函數`fibonacci()`用`tailrec`修飾符標記，并且該函數可進行尾遞歸調用。 因此，在這種情況下，編譯器會優化遞歸。 * * * 如果嘗試在不使用尾部遞歸的情況下找到斐波那契序列的第 20000 項（或任何其他大整數），則編譯器將引發`java.lang.StackOverflowError`異常。 但是，我們上面的程序可以正常工作。 這是因為我們使用了尾部遞歸，它使用了基于循環的高效版本，而不是傳統的遞歸。 * * * ### 示例：使用尾遞歸的階乘 上述示例（第一個示例）中用于計算數字階乘的示例無法針對尾遞歸進行優化。 這是執行相同任務的另一個程序。 ```kt fun main(args: Array<String>) { val number = 5 println("Factorial of $number = ${factorial(number)}") } tailrec fun factorial(n: Int, run: Int = 1): Long { return if (n == 1) run.toLong() else factorial(n-1, run*n) } ``` 運行該程序時，輸出為： ```kt Factorial of 5 = 120 ``` 編譯器可以在此程序中優化遞歸，因為遞歸函數可以進行尾遞歸，并且我們使用了`tailrec`修飾符，告訴編譯器優化遞歸。