Posted on by Kalkicode
Code Recursion

Find minimum element in array using recursion

Recursion is a powerful technique in computer programming, where a function calls itself to solve a smaller version of the same problem. In this article, we will explore how to find the minimum element in an array using recursion. We'll start by explaining the problem statement and then proceed to a suitable example. After that, we'll provide the pseudocode and the algorithm along with their explanations.

Problem Statement

Given an unsorted array of integers, we want to find the smallest element present in the array. We'll use recursion to implement an efficient solution for this problem. The goal is to develop a function that takes an array and its boundaries (low and high) as input and returns the minimum element within that range.

Example

Let's consider the following unsorted array of integers:

[7, 3, 8, 23, 3, 2, 9, 35, 13, 42, 1, 3]

We will find the minimum element using our recursive function.

Pseudocode

Before diving into the algorithm, let's understand the pseudocode that describes the recursive approach:


function min_element(collection, low, high):
	if low equals high:
		return collection[high]
	mid = (low + high) / 2
	a = min_element(collection, low, mid)
	b = min_element(collection, mid + 1, high)
	if a is less than b:
		return a
	else:
		return b

  

The recursive function min_element takes three parameters:

  • collection: The array in which we want to find the minimum element.
  • low: The starting index of the current subarray.
  • high: The ending index of the current subarray.

If the function encounters a subarray with only one element (i.e., when low and high are the same), it returns that single element as the minimum.

Otherwise, the function calculates the middle index mid of the current subarray. It then calls itself twice with two smaller subarrays, one from low to mid and the other from mid + 1 to high. The function then compares the minimum elements found in both subarrays and returns the smaller one as the overall minimum element for the current subarray.

Algorithm Explanation

Let's walk through the algorithm step by step to understand how it works:

  1. Start with an unsorted array and pass it to the min_element function along with low = 0 (the first index) and high = size - 1 (the last index) of the array.
  2. The function checks if low and high are the same (i.e., a single element subarray). If true, it returns the element at that index as the minimum element.
  3. If the subarray has more than one element, the function calculates the middle index mid of the current subarray.
  4. Now, the function makes two recursive calls:
    • One with the low and mid as the boundary to find the minimum element in the left half of the current subarray.
    • The other with mid + 1 and high as the boundary to find the minimum element in the right half of the current subarray.
  5. Finally, the function compares the two minimum elements found in the left and right halves and returns the smaller one as the overall minimum element for the current subarray.

The recursion continues until the subarrays with a single element are reached, and then the minimum elements of each subarray are merged to find the minimum element of the entire array.

Code Solution

Here given code implementation process.

// C program
// Find minimum element in array using recursion
#include <stdio.h>

//Find min element recursively in given collection
int min_element(int collection[], int low, int high)
{
	if (low == high)
	{
		//When only one element then returning current element
		return collection[high];
	}
	// Find mid element
	// low is first element location
	// high is last element location
	int mid = (low + high) >> 1;
	//Find min element in left side
	int a = min_element(collection, low, mid);
	//Find min element in right side
	int b = min_element(collection, mid + 1, high);
	if (a < b)
	{
		// When a is min
		return a;
	}
	else
	{
		// When b is min
		return b;
	}
}
//Display element of given collection
void display_element(int collection[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		printf("  %d", collection[i]);
	}
	printf("\n");
}
int main()
{
	// Define the unsorted array elements
	int collection[] = {
		7,
		3,
		8,
		23,
		3,
		2,
		9,
		35,
		13,
		42,
		1,
		3
	};
	//Get the size of given collection
	int size = sizeof(collection) / sizeof(collection[0]);
	printf("Element : ");
	display_element(collection, size);
	int result = min_element(collection, 0, size - 1);
	printf("Minimum Element : %d \n", result);
	return 0;
}

Output

Element :   7  3  8  23  3  2  9  35  13  42  1  3
Minimum Element : 1
/*
    Java Program
    Find minimum element in array using recursion
*/
class MyRecursion
{
	//Find min element recursively in given collection
	public int min_element(int[] collection, int low, int high)
	{
		if (low == high)
		{
			//When only one element then returning current element
			return collection[high];
		}
		// Find mid element
		// low is first element location
		// high is last element location
		int mid = (low + high) >> 1;
		//Find min element in left side
		int a = min_element(collection, low, mid);
		//Find min element in right side
		int b = min_element(collection, mid + 1, high);
		if (a < b)
		{
			// When a is min
			return a;
		}
		else
		{
			// When b is min
			return b;
		}
	}
	//Display element of given collection
	public void display_element(int[] collection, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			System.out.print(" " + collection[i]);
		}
		System.out.print("\n");
	}
	public static void main(String[] args)
	{
		MyRecursion obj = new MyRecursion();
		// Define the unsorted array elements
		int[] collection = {
			7,
			3,
			8,
			23,
			3,
			2,
			9,
			35,
			13,
			42,
			1,
			3
		};
		//Get the size of given collection
		int size = collection.length;
		System.out.print("Element : ");
		obj.display_element(collection, size);
		int result = obj.min_element(collection, 0, size - 1);
		System.out.print("Minimum Element : " + result + " \n");
	}
}

Output

Element :  7 3 8 23 3 2 9 35 13 42 1 3
Minimum Element : 1
//Include header file
#include <iostream>

using namespace std;
/*
    C++ Program
    Find minimum element in array using recursion
*/
class MyRecursion
{
	public:
		//Find min element recursively in given collection
		int min_element(int collection[], int low, int high)
		{
			if (low == high)
			{
				//When only one element then returning current element
				return collection[high];
			}
			// Find mid element
			// low is first element location
			// high is last element location
			int mid = (low + high) >> 1;
			//Find min element in left side
			int a = this->min_element(collection, low, mid);
			//Find min element in right side
			int b = this->min_element(collection, mid + 1, high);
			if (a < b)
			{
				// When a is min
				return a;
			}
			else
			{
				// When b is min
				return b;
			}
		}
	//Display element of given collection
	void display_element(int collection[], int size)
	{
		for (int i = 0; i < size; ++i)
		{
			cout << " " << collection[i];
		}
		cout << "\n";
	}
};
int main()
{
	MyRecursion obj = MyRecursion();
	// Define the unsorted array elements
	int collection[] = {
		7 , 3 , 8 , 23 , 3 , 2 , 9 , 35 , 13 , 42 , 1 , 3
	};
	//Get the size of given collection
	int size = sizeof(collection) / sizeof(collection[0]);
	cout << "Element : ";
	obj.display_element(collection, size);
	int result = obj.min_element(collection, 0, size - 1);
	cout << "Minimum Element : " << result << " \n";
	return 0;
}

Output

Element :  7 3 8 23 3 2 9 35 13 42 1 3
Minimum Element : 1
//Include namespace system
using System;
/*
    C# Program
    Find minimum element in array using recursion
*/
class MyRecursion
{
	//Find min element recursively in given collection
	public int min_element(int[] collection, int low, int high)
	{
		if (low == high)
		{
			//When only one element then returning current element
			return collection[high];
		}
		// Find mid element
		// low is first element location
		// high is last element location
		int mid = (low + high) >> 1;
		//Find min element in left side
		int a = min_element(collection, low, mid);
		//Find min element in right side
		int b = min_element(collection, mid + 1, high);
		if (a < b)
		{
			// When a is min
			return a;
		}
		else
		{
			// When b is min
			return b;
		}
	}
	//Display element of given collection
	public void display_element(int[] collection, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			Console.Write(" " + collection[i]);
		}
		Console.Write("\n");
	}
	public static void Main(String[] args)
	{
		MyRecursion obj = new MyRecursion();
		// Define the unsorted array elements
		int[] collection = {
			7 , 3 , 8 , 23 , 3 , 2 , 9 , 35 , 13 , 42 , 1 , 3
		};
		//Get the size of given collection
		int size = collection.Length;
		Console.Write("Element : ");
		obj.display_element(collection, size);
		int result = obj.min_element(collection, 0, size - 1);
		Console.Write("Minimum Element : " + result + " \n");
	}
}

Output

Element :  7 3 8 23 3 2 9 35 13 42 1 3
Minimum Element : 1
<?php
/*
    Php Program
    Find minimum element in array using recursion
*/
class MyRecursion
{
	//Find min element recursively in given collection
	public	function min_element( & $collection, $low, $high)
	{
		if ($low == $high)
		{
			//When only one element then returning current element
			return $collection[$high];
		}
		// Find mid element
		// low is first element location
		// high is last element location
		$mid = ($low + $high) >> 1;
		//Find min element in left side
		$a = $this->min_element($collection, $low, $mid);
		//Find min element in right side
		$b = $this->min_element($collection, $mid + 1, $high);
		if ($a < $b)
		{
			// When a is min
			return $a;
		}
		else
		{
			// When b is min
			return $b;
		}
	}
	//Display element of given collection
	public	function display_element( & $collection, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			echo " ". $collection[$i];
		}
		echo "\n";
	}
}

function main()
{
	$obj = new MyRecursion();
	// Define the unsorted array elements
	$collection = array(7, 3, 8, 23, 3, 2, 9, 35, 13, 42, 1, 3);
	//Get the size of given collection
	$size = count($collection);
	echo "Element : ";
	$obj->display_element($collection, $size);
	$result = $obj->min_element($collection, 0, $size - 1);
	echo "Minimum Element : ". $result ." \n";
}
main();

Output

Element :  7 3 8 23 3 2 9 35 13 42 1 3
Minimum Element : 1
/*
    Node Js Program
    Find minimum element in array using recursion
*/
class MyRecursion
{
	//Find min element recursively in given collection
	min_element(collection, low, high)
	{
		if (low == high)
		{
			//When only one element then returning current element
			return collection[high];
		}
		// Find mid element
		// low is first element location
		// high is last element location
		var mid = (low + high) >> 1;
		//Find min element in left side
		var a = this.min_element(collection, low, mid);
		//Find min element in right side
		var b = this.min_element(collection, mid + 1, high);
		if (a < b)
		{
			// When a is min
			return a;
		}
		else
		{
			// When b is min
			return b;
		}
	}
	//Display element of given collection
	display_element(collection, size)
	{
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write(" " + collection[i]);
		}
		process.stdout.write("\n");
	}
}

function main()
{
	var obj = new MyRecursion();
	// Define the unsorted array elements
	var collection = [7, 3, 8, 23, 3, 2, 9, 35, 13, 42, 1, 3];
	//Get the size of given collection
	var size = collection.length;
	process.stdout.write("Element : ");
	obj.display_element(collection, size);
	var result = obj.min_element(collection, 0, size - 1);
	process.stdout.write("Minimum Element : " + result + " \n");
}
main();

Output

Element :  7 3 8 23 3 2 9 35 13 42 1 3
Minimum Element : 1
#  Python 3 Program
#  Find minimum element in array using recursion

class MyRecursion :
	# Find min element recursively in given collection
	def min_element(self, collection, low, high) :
		if (low == high) :
			# When only one element then returning current element
			return collection[high]
		
		#  Find mid element
		#  low is first element location
		#  high is last element location
		mid = (low + high) >> 1
		# Find min element in left side
		a = self.min_element(collection, low, mid)
		# Find min element in right side
		b = self.min_element(collection, mid + 1, high)
		if (a < b) :
			#  When a is min
			return a
		else :
			#  When b is min
			return b
		
	
	# Display element of given collection
	def display_element(self, collection, size) :
		i = 0
		while (i < size) :
			print(" ", collection[i], end = "")
			i += 1
		
		print("\n", end = "")
	

def main() :
	obj = MyRecursion()
	#  Define the unsorted array elements
	collection = [7, 3, 8, 23, 3, 2, 9, 35, 13, 42, 1, 3]
	# Get the size of given collection
	size = len(collection)
	print("Element : ", end = "")
	obj.display_element(collection, size)
	result = obj.min_element(collection, 0, size - 1)
	print("Minimum Element : ", result ," \n", end = "")

if __name__ == "__main__": main()

Output

Element :   7  3  8  23  3  2  9  35  13  42  1  3
Minimum Element :  1
#  Ruby Program
#  Find minimum element in array using recursion

class MyRecursion

	# Find min element recursively in given collection
	def min_element(collection, low, high)
	
		if (low == high)
		
			# When only one element then returning current element
			return collection[high]
		end
		#  Find mid element
		#  low is first element location
		#  high is last element location
		mid = (low + high) >> 1
		# Find min element in left side
		a = self.min_element(collection, low, mid)
		# Find min element in right side
		b = self.min_element(collection, mid + 1, high)
		if (a < b)
		
			#  When a is min
			return a
		else
		
			#  When b is min
			return b
		end
	end
	# Display element of given collection
	def display_element(collection, size)
	
		i = 0
		while (i < size)
		
			print(" ", collection[i])
			i += 1
		end
		print("\n")
	end
end
def main()

	obj = MyRecursion.new()
	#  Define the unsorted array elements
	collection = [7, 3, 8, 23, 3, 2, 9, 35, 13, 42, 1, 3]
	# Get the size of given collection
	size = collection.length
	print("Element : ")
	obj.display_element(collection, size)
	result = obj.min_element(collection, 0, size - 1)
	print("Minimum Element : ", result ," \n")
end
main()

Output

Element :  7 3 8 23 3 2 9 35 13 42 1 3
Minimum Element : 1 
/*
    Scala Program
    Find minimum element in array using recursion
*/
class MyRecursion
{
	//Find min element recursively in given collection
	def min_element(collection: Array[Int], low: Int, high: Int): Int = {
		if (low == high)
		{
			//When only one element then returning current element
			return collection(high);
		}
		// Find mid element
		// low is first element location
		// high is last element location
		var mid: Int = (low + high) >> 1;
		//Find min element in left side
		var a: Int = min_element(collection, low, mid);
		//Find min element in right side
		var b: Int = min_element(collection, mid + 1, high);
		if (a < b)
		{
			// When a is min
			return a;
		}
		else
		{
			// When b is min
			return b;
		}
	}
	//Display element of given collection
	def display_element(collection: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			print(" " + collection(i));
			i += 1;
		}
		print("\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyRecursion = new MyRecursion();
		// Define the unsorted array elements
		var collection: Array[Int] = Array(7, 3, 8, 23, 3, 2, 9, 35, 13, 42, 1, 3);
		//Get the size of given collection
		var size: Int = collection.length;
		print("Element : ");
		obj.display_element(collection, size);
		var result: Int = obj.min_element(collection, 0, size - 1);
		print("Minimum Element : " + result + " \n");
	}
}

Output

Element :  7 3 8 23 3 2 9 35 13 42 1 3
Minimum Element : 1
/*
    Swift Program
    Find minimum element in array using recursion
*/
class MyRecursion
{
	//Find min element recursively in given collection
	func min_element(_ collection: [Int], _ low: Int, _ high: Int) -> Int
	{
		if (low == high)
		{
			//When only one element then returning current element
			return collection[high];
		}
		// Find mid element
		// low is first element location
		// high is last element location
		let mid: Int = (low + high) >> 1;
		//Find min element in left side
		let a: Int = self.min_element(collection, low, mid);
		//Find min element in right side
		let b: Int = self.min_element(collection, mid + 1, high);
		if (a < b)
		{
			// When a is min
			return a;
		}
		else
		{
			// When b is min
			return b;
		}
	}
	//Display element of given collection
	func display_element(_ collection: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print(" ", collection[i], terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
}
func main()
{
	let obj: MyRecursion = MyRecursion();
	// Define the unsorted array elements
	let collection: [Int] = [7, 3, 8, 23, 3, 2, 9, 35, 13, 42, 1, 3];
	//Get the size of given collection
	let size: Int = collection.count;
	print("Element : ", terminator: "");
	obj.display_element(collection, size);
	let result: Int = obj.min_element(collection, 0, size - 1);
	print("Minimum Element : ", result ," \n", terminator: "");
}
main();

Output

Element :   7  3  8  23  3  2  9  35  13  42  1  3
Minimum Element :  1

Resultant Output Explanation

Now, let's see how our recursive function works with the given example array:

    [7, 3, 8, 23, 3, 2, 9, 35, 13, 42, 1, 3]
  

Initially, the function is called with low = 0 and high = 11 (size - 1). It calculates mid = (0 + 11) / 2 = 5. The function then makes two recursive calls:

    First call: min_element(collection, 0, 5)
    Second call: min_element(collection, 6, 11)
  

Now, the two recursive calls result in:

    First call: min_element(collection, 0, 2)
    Second call: min_element(collection, 6, 8)
  

The process continues until we reach the subarrays with single elements:

    First call: min_element(collection, 0, 0) -> returns 7
    Second call: min_element(collection, 1, 1) -> returns 3
    ...
    ...
    First call: min_element(collection, 10, 10) -> returns 1
    Second call: min_element(collection, 11, 11) -> returns 3
  

Finally, the function compares the minimum elements from both sides and returns the smallest one:

    Final call: min_element(collection, 0, 11) -> compares 7 and 1, returns 1
  

Thus, the minimum element in the array is 1, which is correctly identified by our recursive function.

Time Complexity of the Algorithm

The time complexity of finding the minimum element using recursion is O(n), where n is the number of elements in the array. This is because the function divides the array into smaller halves at each recursive call, and the number of calls is proportional to the number of elements.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment