Yogesh Choudhary Paliyal
Yogesh Paliyal's Blog

Yogesh Paliyal's Blog

Types of Recursion

Yogesh Choudhary Paliyal
·Oct 24, 2021·

2 min read

Subscribe to my newsletter and never miss my upcoming articles

Listen to this article

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!

Learn more about Hashnode Sponsors
 
Share this