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.

Categories
Relative Post