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.
Example: Find the factorial of a Number using Recursion
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)
}
How this program works?
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
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.
The recursive call must be the last call of the method.
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