Recursion
Calling same function inside function is known as Recursion.
Every recurring function must have a breaking condition which break recursion.
Time taken by Recursion
 O(n) if there is no loop inside the recursion
Types of Recursion
1. Tail Recursion
 Recurring function is called at end of all the statements.
 There should not be handling of return type.

Tail Recursion can be converted to loop easily
Example:
fun main(){ fun1(5) } /* Example with recursion * Time > O(n) * Space > O(n) */ fun fun1(n){ if(n > 0){ print(n) fun1(n1) // tail recursion } } /* * Converted to while loop * Time > O(n) * Space > O(1) */ fun fun1(n){ while(n > 0){ print(n) n } }
2. Head Recursion
Recurring function is called at start before any statements, just after the break condition.
Example:
fun main() {
fun1(5)
}
fun fun1(n) {
if (n > 0) {
fun1(n  1) // head recursion
print(n)
}
}
3. Tree Recursion
More than once the self function is called from inside the function
Example:
fun main() {
fun1(5)
}
fun fun1(n) {
if (n > 0) {
fun1(n  1) // tree recursion
fun1(n  1) // tree recursion
print(n)
}
}
4. Indirect Recursion
Recurring via multiple loops, like function A calls B and B calls A
Example:
fun main(){
funA(5)
}
fun funA(n: Int){
if (n > 0){
funB(n1)
}
}
fun funB(n: Int){
funA(n)
}
5. Nested Recursion
Function is calling itself with returning value and that will be used to call self function.
Example:
fun main(){
fun1(90)
}
fun fun1(n){
return if(n > 100){
n  10
}else{
fun1(fun1(n + 11)) // Nested recursion
}
}
Top comments (0)