In programming terms, a recursive function can be defined as a routine that calls itself directly or indirectly. Using the recursive algorithm, certain problems can be solved quite easily.

Introduction

A recursive function is a function that calls itself, directly or indirectly.

A recursive method consists of two parts: Termination Condition and Body (which include recursive expansion).

Termination Condition: A recursive method always contains one or more terminating condition. A condition in which recursive method process a simple case and do not call itself.
Body: (including recursive expansion): The main logic of the recursive method contained in the body of the method. It also contains the recursion expansion statement that in turn calls the method itself.

Three important properties of recursive algorithm are:

A recursive algorithm must have a termination condition.
A recursive algorithm must change its state, and move towards the termination condition.
A recursive algorithm must call itself.

Note: The speed of a recursive program is slower because of stack overheads. If the same task can be done using an iterative solution (using loops), then we should prefer an iterative solution in place of recursion to avoid stack overhead.

Note: Without termination condition, the recursive method may run forever and will finally consume all the stack memory.

Recursive Function

Some common applications will be exemplified below, and recursive approaches will be used to solve them. Of course, recursion is not necessarily the optimal solution for them, and is mainly intended to illustrate recursive functions.

Factorial

The factorial of a number is the function that multiplies the number by every natural number below it. Symbolically, factorial can be represented as !. So, n factorial is the product of the first n natural numbers and is represented as n. The formula for n factorial is:

$$n!=n\times \left( n-1\right) \times \ldots \times 1$$

Factorial Calculation:

//Factorial calculation N!= N*(N-1)...2*1
func Factorial(n int) int {
	// termination condition
	if n <= 1 {
		return 1
	}

	// body, recursive expansion
	return n * Factorial(n-1)
}

Analysis: Factorial() function is calling itself bask inside the function. Continue calling itself recursively until you call the Factorial(1) function.

Time Complexity is $O(N)$.

Fibonacci number

For more information about fibonacci numbers sequence, please refer to the-fibonacci-sequence. The formula for fibonacci numbers is:

$$F_0=0$$

$$F_1=1$$

Given N find the Nth number in the Fibonacci series:

// Fibonacci Given N find the Nth number in the Fibonacci series
func Fibonacci(n int) int {
	if n <= 1 {
		return n
	}

	return Fibonacci(n-1) + Fibonacci(n-2)
}

Analysis: Fibonacci number are calculated by adding sum of the previous two number.

There is an inefficiency in the solution we will look better solution in coming.

Tower of Hanoi

The Tower of Hanoi (also called the Tower of Brahma) We are given three rods and N number of disks, initially all the disks are added to first rod (the leftmost one) in decreasing size order. The objective is to transfer the entire stack of disks from first tower to third tower (the rightmost one), moving only one disk at a time and never a larger one onto a smaller.

This is a very interesting game that you can play it online Play Tower of Hanoi, have fun O(∩_∩)O

// TOHUtil Use the peg to move the disk
func TOHUtil(num int, from, to, temp string) {
	if num < 1 {
		return
	}

	TOHUtil(num-1, from, temp, to)
	fmt.Println("Move disk", num, "from peg", from, "to peg", to)
	TOHUtil(num-1, temp, to, from)
}

// TowersOfHanoi Call TOHUtil function completion the operation of moving the disk
func TowersOfHanoi(num int) {
	fmt.Println("The sequence of moves involved in the Tower of Hanoi are:")
	TOHUtil(num, "A", "B", "C")
}

Analysis: To move N disks from source to destination, we first move N-1 disks from source to temp then move the lowest Nth disk from source to destination. Then will move N-1 disks from temp to destination.

Greatest common divisor (GCD)

The greatest common divisor (GCD) refers to the greatest positive integer that is a common divisor for a given set of positive integers. It is also termed as the highest common factor (HCF) or the greatest common factor (GCF). The formula for gcd is:

$$lcm\left( a,b\right) =\dfrac{\left| a\cdot b\right| }{\gcd \left( a,b\right) }$$

Ok, use Euclid’s algorithm to find gcd. GCD(n, m) == GCD(m, n mod m):

// Gcd Find the greatest common divisor
func Gcd(m, n int) int {
	if m < n {
		return Gcd(n, m)
	}

	if m%n == 0 {
		return n
	}

	return Gcd(n, m%n)
}

All permutations of an integer list

Generate all permutations of an integer list:

// printSlice Format print the slice, length, capacity
func printSlice(data []int) {
	fmt.Printf("%v: len=%d cap=%d\n", data, len(data), cap(data))
}

// swap the positions of two numbers
func swap(data []int, a, b int) {
	data[a], data[b] = data[b], data[a]
}

// Permutation Generate all permutations of an integer list
func Permutation(data []int, n, length int) {
	if length == n {
		printSlice(data)
		return
	}

	for m := n; m < length; m++ {
		swap(data, n, m)
		Permutation(data, n+1, length)
		swap(data, n, m)
	}
}

Analysis: In permutation method at each recursive call number at index, “i” is swapped with all the numbers that are right of it. Since the number is swapped with all the numbers in its right one by one it will produce all the permutation possible.

Binary search using recursion

Search a value in an increasing order sorted list of integers:

// BinarySearchRecursive Search a value in an increasing order sorted list of integers
func BinarySearchRecursive(data []int, low, high, value int) int {
	mid := low + (high-low)/2 // To afunc the overflow

	if data[mid] == value {
		return mid
	} else if data[mid] < value {
		return BinarySearchRecursive(data, mid+1, high, value)
	} else {
		return BinarySearchRecursive(data, low, mid-1, value)
	}
}

Analysis: Similar iterative solution we had already seen. Now let us look into the recursive solution of the same problem. In this solution, we are diving the search space into half and discarding the rest. This solution is very efficient as each step we are rejecting half the search space / list.

Conclusion

In this recursive algorithm post, you learned what a recursive algorithm in Go programming is. After that, you looked at the programming to implement recursive applications. The full sample code and test cases can be viewed in my GitHub repo. I hope this is helpful to you, and thank you for reading.

Recursive Algorithm and Applications

Table of Contents