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