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

Did you find this article valuable?

Support Yogesh Choudhary Paliyal by becoming a sponsor. Any amount is appreciated!