Function - Recursion and Tail Recursion
Recursion function
is a function that calls itself continuously. This technique is called recursion,
Tail recursion
is a recursion that performs the calculation first, then makes the recursive call. The result of the current step is passed into the next recursive call.
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)
}
Here are the steps involved:
factorial(4) // st function call. Argument: 4
4*factorial(3) // nd function call. Argument: 3
4*(3*factorial(2)) // rd function call. Argument: 2
4*(3*(2*factorial(1))) // th function call. Argument: 1
4*(3*(2*1))
24
Tail recursion
To tell the compiler to perform tail recursion in Kotlin, you need to mark the function with tailrec modifier.
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)
}
}
Output:
Factorial of 4 = 24
Comments
Post a Comment