# Types of Recursion

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

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