Follow

Follow

# Types of Recursion

Yogesh Choudhary Paliyal
·Oct 24, 2021·

## 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(n-1) // tail recursion
}
}
/*
* Converted to while loop
* Time -> O(n)
* Space -> O(1)
*/
fun fun1(n){
while(n > 0){
print(n)
n--
}
}
``````

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(n-1)
}
}

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
}
}
``````