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