DEV Community

Yogesh Choudhary Paliyal
Yogesh Choudhary Paliyal

Posted on

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)
      }
  }
Enter fullscreen mode Exit fullscreen mode

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)
      }
  }
Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Top comments (0)