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