go-tutorial

Go Recursion

Recursion is a type of programming code in which a method or function repeatedly calls itself.

The Go programming language supports recursion through functions. A recursive function is one that calls itself. Code written in this manner is simple to write but difficult to comprehend.

Criteria of Recursion

The most important aspects of the recursion function.

  • Within the same function, another function is called.
  • In a recursive function, it’s always a good idea to include an exit condition.
  • It lowers the number of unneeded function calls and lines of code.
  • The disadvantages of recursion are that the code is logical and difficult to debug and analyse.

Golang’s Recursion Syntax

// function declaration  
func recursefunction(){  
//Code statements  
recursefunction();//function call itself  
}  
func main(){  
recursefunction() // Initialize first normal call  
}  

In the above syntax, the recursive function is called from within another function. The recursion procedure continues until the condition is satisfied. Otherwise, the code executes in an infinite loop. If the block conducts recursive calls, then the else block will interrupt the recursive call, preventing infinite recursion.

Types of recursion

As previously stated, there are two types of recursion. The finite or ordinary recursion comes first, followed by infinite recursion. Let’s have a look at what they are.

1. Finite Recursion

When a recursion ends after a finite number of recursive calls, it is known as finite recursion. Only when a base condition is met does a recursion come to an end.

Recursion, often known as finite recursion or just recursion, is a condition of function in which:

  • The function is invoked by itself.
  • It comes to a halt when it reaches the boundary condition.

An example of a finite recursion is shown below.

package main
 
import (
    "fmt"
)
 
func recurFact(v int) int {
    if (v == 0) { 
        return 1
    } else { 
        return v * recurFact(v-1) 
    }
}
 
func main() {
    n := recurFact(10)
     
    fmt.Println(n)         // 3628800
}

2. Infinite recursion

When the second criterion is not met, infinite recursion occurs. To put it another way, the function never stops calling itself. This is an example of an endless recursion in action.

package main
 
import (
    "fmt"
)
 
func recurse() {
    fmt.Println("Endless!")
    recurse()
}
 
func main() {
    // recurse() // infinite call
}

Methods of recursion

Recursion can be split into two types based on the methods or order in which it calls itself. The first is a conventional one, whereas the second is a tail-recursive one. Let’s take a look at each of them individually.

1. Recursion on a regular basis

Regular recursion occurs when a call to itself does not instantly complete the calculation, but instead passes it down the hierarchy. This is demonstrated in the example below.

package main
 
import (
    "fmt"
)
 
func fib(n int) int {
    if (n == 0) {
        return 0
    } else if(n == 1) {
        return 1
    } else {
        return fib(n-1) + fib(n-2)
    }
}
 
func main() {
    fmt.Println(fib(10))  // 55
}

2. Tail-recursion

When a function calls itself, it calculates the value and passes it down the hierarchy, which is known as tail recursion. An example of a tail-recursion is shown below.

package main
 
import (
    "fmt"
)
 
func f(v int) {
    if(v == 0) {
        fmt.Println("Zero")
        return
    } else {
        fmt.Println(v)
        f(v-1) // tail-recursive call
    }
}
 
func main() {
    f(5)
     
    // output:
    // 5
    // 4
    // 3
    // 2
    // 1
    // Zero
}

Benefits of tail-recursion

Tail-calls are advantageous in that they are frequently optimised by compilers. As a result, it is nearly always faster than a standard recursive call.

RECOMMENDED ARTICLES





Leave a Reply

Your email address will not be published. Required fields are marked *