Different Types of Recursion in Golang

Recursion in Go (Golang) refers to a programming technique where a function calls itself directly or indirectly to solve a problem. There are different types of recursion that can be applied in Go based on how the recursive calls are made and the structure of the recursive function.

1. Linear Recursion: In linear recursion, a function calls itself exactly once in each recursive call. This type of recursion follows a linear sequence until reaching a base case that terminates the recursion.
2. Tail Recursion: Tail recursion occurs when a recursive call is the last operation performed by the function before returning its result. Tail-recursive functions can be optimized by compilers into iterative loops, reducing stack space usage.
3. Binary Recursion: Binary recursion involves a function making two recursive calls in each invocation. This type of recursion is common in algorithms dealing with binary trees or divide-and-conquer problems.
4. Nested Recursion: Nested recursion occurs when a recursive function calls itself with a recursive call as an argument. This type of recursion can lead to complex patterns of function invocations.

1. Direct Recursion : Program to illustrate the Fibonacci series

   package main
   import "fmt"
   
   func fib(i int) int {
   
       if i == 0 {
           return 1
       }
       if i == 1 {
           return 1
       }
       return fib(i-1) + fib(i-2)
   }
   func main() {
       var i int
       for i = 0; i < 10; i++ {
           fmt.Printf("%d \n", fib(i))
   
       }
   }
   

   Output :

   PS C:\GO_Language\recursion> go run recursion.go
   1 
   1 
   2 
   3 
   5 
   8 
   13 
   21 
   34 
   55
   

    

2. Indirect Recursion:  Program to illustrate indirect recursion between two functions.

   package main
   import "fmt"
   
   func print_one(n int) {
       if n >= 0 {
           fmt.Println("In first function:", n)
           print_two(n - 1)
       }
   }
   
   func print_two(n int) {
   
       if n >= 0 {
           fmt.Println("In second function:", n)
           print_one(n - 1)
       }
   }
   
   func main() {
       print_one(10)
       print_one(-1)
   }
   

   Output :

   PS C:\GO_Language\recursion> go run indirect_re.go
   
   In first function: 10
   In second function: 9
   In first function: 8
   In second function: 7
   In first function: 6
   In second function: 5
   In first function: 4
   In second function: 3
   In first function: 2
   In second function: 1
   In first function: 0
   

    

3. Tail recursion :  Golang program to illustrate the concept of tail recursion

   package main
   
   import (
       "fmt"
   )
   
   // tail-recursive function to print all numbers from n to 1
   func print_num(n int) {
   
       // if a number is still  positive, print it and call the function with the decremented value
       if n > 0 {
           fmt.Println(n)
   
           //  last statement in  the recursive function tail recursive call
           print_num(n - 1)
       }
   }
   
   // main function
   func main() {
   
       // passing a positive number, prints 5 to 1
       print_num(5)
   }
   

   Output :

   PS C:\GO_Language\recursion> go run rec3.go       
   5
   4
   3
   2
   1
   

    

4. Head Recursion : Golang program to illustrate the concept of head recursion

   package main
   
   import (
       "fmt"
   )
   
   func print_num(n int) {
   
       if n > 0 {
           print_num(n - 1)
           fmt.Println(n)
       }
   }
   func main() {
       print_num(5)
   }
   

   Output :

   PS C:\GO_Language\recursion> go run rec4.go
   1
   2
   3
   4
   5
   

    

5. Infinite Recursion :Infinite repetition occurs when the second condition is not followed. , There’s an infinite recursion in action here

   package main
   
   import (
       "fmt"
   )
   
   func print_hello() {
       fmt.Println("Prwatech")
       print_hello()
   }
   func main() {
       print_hello()
   }
   

   Output :

   PS C:\GO_Language\recursion> go run rec5.go
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   Prwatech
   
   exit status 0xc000013a
   

   Different Types of Recursion in Golang