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