Kotlin遞歸函數

遞歸函數是一個連續調用自身的函數。 這種技術稱為遞歸。

語法

fun functionName(){
    .. .. ..
    functionName() //調用函數自身
}

Kotlin遞歸函數示例1：有限次數

下麵來看看一個遞歸函數列印計數的例子。

var count = 0
fun rec(){
    count++;
    if(count<=5){
        println("count => "+count);
        rec();
    }
}
fun main(args: Array<String>) {
    rec();
}

執行上面示例代碼，得到以下結果 -

count => 1
count => 2
count => 3
count => 4
count => 5

Kotlin遞歸函數示例2：階乘數

下麵我們來看一個計算階乘數的遞歸函數的例子。

fun main(args: Array<String>) {
    val number = 5
    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)
    }
}

執行上面示例代碼，得到以下結果 -

Factorial of 5 = 120

上述階乘實例的工作過程 -

factorial(5)
   factorial(4)
      factorial(3)
         factorial(2)
            factorial(1)
               return 1
            return 2*1 = 2
         return 3*2 = 6
      return 4*6 = 24
   return 5*24 = 120

Kotlin尾遞歸

在討論學習尾遞歸之前，先來嘗試使用一般(正常)遞歸來計算第n個(上限數為100000)的總和。

一般遞歸
下麵來看使用一般(正常)遞歸計算第n個(上限數為100000)之和的示例。

fun main(args: Array<String>) {
    var result = recursiveSum(100000)
    println(result)
}
fun recursiveSum(n: Long) : Long {
    return if (n <= 1) {
        n
    } else {
        n + recursiveSum(n - 1)
    }
}

執行上面示例代碼，得到類似以下結果 -

.....
jdk7.jar;C:\Users\hema\.IdeaIC2018.3\config\plugins\Kotlin\kotlinc\lib\kotlin-stdlib-jdk8.jar" HelloWorldKt
Exception in thread "main" java.lang.StackOverflowError
    at HelloWorldKt.recursiveSum(HelloWorld.kt:9)
    at HelloWorldKt.recursiveSum(HelloWorld.kt:9)
    at HelloWorldKt.recursiveSum(HelloWorld.kt:9)

上面的示例拋出了“java.lang.StackOverflowError” 的異常。 這是因為編譯器無法調用大量的遞歸函數調用。

尾遞歸

尾遞歸是一種遞歸，它首先執行計算，然後進行遞歸調用。 當前步驟的結果被傳遞到下一個遞歸調用。

尾遞歸遵循一個實現規則。 該規則如下：

遞歸調用必須是方法的最後一次調用。 要將遞歸聲明為尾遞歸，我們需要在遞歸函數之前使用tailrec修飾符。

Kotlin尾遞歸示例1：計算n(100000)個整數之和
下麵來看一個使用尾遞歸計算第n個(上限為100000)之和的示例。

fun main(args: Array<String>) {
    var number = 100000.toLong()
    var result = recursiveSum(number)
    println("sum of upto $number number = $result")
}
tailrec fun recursiveSum(n: Long, semiresult: Long = 0) : Long {
    return if (n <= 0) {
        semiresult
    } else {
        recursiveSum( (n - 1), n+semiresult)
    }
}

執行上面示例代碼，得到以下結果 -

sum of upto 100000 number = 5000050000

Kotlin尾遞歸示例2：計算數字階乘

下麵來看一個使用尾遞歸計算數字階乘的示例。

fun main(args: Array<String>) {
    val number = 4
    val result: Long
    result = factorial(number)
    println("Factorial of $number = $result")
}

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

執行上面示例代碼，得到以下結果 -

Factorial of 4 = 24