Find max element in array using recursion
Recursion is a programming technique where a function calls itself to solve a smaller subproblem of the main problem. In this article, we will explore how to find the maximum element in an array using recursion. We will discuss the problem statement, provide an explanation with a suitable example, and then present the pseudocode and algorithm for the solution. Finally, we will analyze the time complexity of the code.
Problem Statement
Given an array of integers, we want to find the maximum element in the array using recursion. The task is to design a recursive function that efficiently determines the maximum element in the array and returns it as the output.
Explanation with Example
Let's consider the following array of integers as an example:
[7, 33, 28, 23, 0, 2, 9, 35, 13, 42, 1, 3]
To find the maximum element in the array using recursion, we divide the array into two halves and find the maximum of each half. Then, we compare the two maximum values and return the larger one as the result.
For our example, the recursion process can be illustrated as follows:
[7, 33, 28, 23, 0, 2] [9, 35, 13, 42, 1, 3]
(Divide into two halves)
Compare the maximum of the two halves:
Max of first half: 33 (recursive call to the left half)
Max of second half: 42 (recursive call to the right half)
The maximum of the entire array: 42 (since 42 > 33)
Pseudocode
The pseudocode for finding the maximum element in an array using recursion is as follows:
function max_element(collection[], low, high)
if low is equal to high
return collection[high]
mid = (low + high) / 2
a = max_element(collection, low, mid)
b = max_element(collection, mid + 1, high)
if a > b
return a
else
return b
Algorithm Explanation
The function max_element
takes three parameters: collection
, low
, and
high
. It finds the maximum element in the given array collection
within the range from index
low
to index high
.
If the range contains only one element (i.e., low
is equal to high
), the function returns that
element as the maximum. Otherwise, it divides the range into two halves using the mid
index and makes recursive
calls to find the maximum of the left half (a
) and the maximum of the right half (b
).
Finally, the function compares a
and b
and returns the larger of the two as the maximum element
for the given range.
Code Solution
Here given code implementation process.
// C program
// Find max element in array using recursion
#include <stdio.h>
//Find max element recursively in given collection
int max_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 max element in left side
int a = max_element(collection, low, mid);
//Find max element in right side
int b = max_element(collection, mid + 1, high);
if (a > b)
{
// When a is max
return a;
}
else
{
// When b is max
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 collection of integer elements
int collection[] = {
7,
33,
28,
23,
0,
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 = max_element(collection, 0, size - 1);
printf("Max Element : %d \n", result);
return 0;
}
Output
Element : 7 33 28 23 0 2 9 35 13 42 1 3
Max Element : 42
/*
Java Program
Find max element in array using recursion
*/
class MyRecursion
{
//Find max element recursively in given collection
public int max_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 max element in left side
int a = max_element(collection, low, mid);
//Find max element in right side
int b = max_element(collection, mid + 1, high);
if (a > b)
{
// When a is max
return a;
}
else
{
// When b is max
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");
}
// main function to test
public static void main(String[] args)
{
MyRecursion obj = new MyRecursion();
// Define the collection of integer elements
int[] collection = {
7,
33,
28,
23,
0,
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.max_element(collection, 0, size - 1);
System.out.print("Max Element : " + result + " \n");
}
}
Output
Element : 7 33 28 23 0 2 9 35 13 42 1 3
Max Element : 42
//Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Find max element in array using recursion
*/
class MyRecursion
{
public:
//Find max element recursively in given collection
int max_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 max element in left side
int a = this->max_element(collection, low, mid);
//Find max element in right side
int b = this->max_element(collection, mid + 1, high);
if (a > b)
{
// When a is max
return a;
}
else
{
// When b is max
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()
// main function to test
{
MyRecursion obj = MyRecursion();
// Define the collection of integer elements
int collection[] = {
7 , 33 , 28 , 23 , 0 , 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.max_element(collection, 0, size - 1);
cout << "Max Element : " << result << " \n";
return 0;
}
Output
Element : 7 33 28 23 0 2 9 35 13 42 1 3
Max Element : 42
//Include namespace system
using System;
/*
C# Program
Find max element in array using recursion
*/
class MyRecursion
{
//Find max element recursively in given collection
public int max_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 max element in left side
int a = max_element(collection, low, mid);
//Find max element in right side
int b = max_element(collection, mid + 1, high);
if (a > b)
{
// When a is max
return a;
}
else
{
// When b is max
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");
}
// main function to test
public static void Main(String[] args)
{
MyRecursion obj = new MyRecursion();
// Define the collection of integer elements
int[] collection = {
7 , 33 , 28 , 23 , 0 , 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.max_element(collection, 0, size - 1);
Console.Write("Max Element : " + result + " \n");
}
}
Output
Element : 7 33 28 23 0 2 9 35 13 42 1 3
Max Element : 42
<?php
/*
Php Program
Find max element in array using recursion
*/
class MyRecursion
{
//Find max element recursively in given collection
public function max_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 max element in left side
$a = $this->max_element($collection, $low, $mid);
//Find max element in right side
$b = $this->max_element($collection, $mid + 1, $high);
if ($a > $b)
{
// When a is max
return $a;
}
else
{
// When b is max
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()
// main function to test
{
$obj = new MyRecursion();
// Define the collection of integer elements
$collection = array(7, 33, 28, 23, 0, 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->max_element($collection, 0, $size - 1);
echo "Max Element : ". $result ." \n";
}
main();
Output
Element : 7 33 28 23 0 2 9 35 13 42 1 3
Max Element : 42
/*
Node Js Program
Find max element in array using recursion
*/
class MyRecursion
{
//Find max element recursively in given collection
max_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 max element in left side
var a = this.max_element(collection, low, mid);
//Find max element in right side
var b = this.max_element(collection, mid + 1, high);
if (a > b)
{
// When a is max
return a;
}
else
{
// When b is max
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()
// main function to test
{
var obj = new MyRecursion();
// Define the collection of integer elements
var collection = [7, 33, 28, 23, 0, 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.max_element(collection, 0, size - 1);
process.stdout.write("Max Element : " + result + " \n");
}
main();
Output
Element : 7 33 28 23 0 2 9 35 13 42 1 3
Max Element : 42
# Ruby Program
# Find max element in array using recursion
class MyRecursion
# Find max element recursively in given collection
def max_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 max element in left side
a = self.max_element(collection, low, mid)
# Find max element in right side
b = self.max_element(collection, mid + 1, high)
if (a > b)
# When a is max
return a
else
# When b is max
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()
# main function to test
obj = MyRecursion.new()
# Define the collection of integer elements
collection = [7, 33, 28, 23, 0, 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.max_element(collection, 0, size - 1)
print("Max Element : ", result ," \n")
end
main()
Output
Element : 7 33 28 23 0 2 9 35 13 42 1 3
Max Element : 42
/*
Scala Program
Find max element in array using recursion
*/
class MyRecursion
{
//Find max element recursively in given collection
def max_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 max element in left side
var a: Int = max_element(collection, low, mid);
//Find max element in right side
var b: Int = max_element(collection, mid + 1, high);
if (a > b)
{
// When a is max
return a;
}
else
{
// When b is max
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 =
// main function to test
{
var obj: MyRecursion = new MyRecursion();
// Define the collection of integer elements
var collection: Array[Int] = Array(7, 33, 28, 23, 0, 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.max_element(collection, 0, size - 1);
print("Max Element : " + result + " \n");
}
}
Output
Element : 7 33 28 23 0 2 9 35 13 42 1 3
Max Element : 42
/*
Swift Program
Find max element in array using recursion
*/
class MyRecursion
{
//Find max element recursively in given collection
func max_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 max element in left side
let a: Int = self.max_element(collection, low, mid);
//Find max element in right side
let b: Int = self.max_element(collection, mid + 1, high);
if (a > b)
{
// When a is max
return a;
}
else
{
// When b is max
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()
// main function to test
{
let obj: MyRecursion = MyRecursion();
// Define the collection of integer elements
let collection: [Int] = [7, 33, 28, 23, 0, 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.max_element(collection, 0, size - 1);
print("Max Element : ", result ," \n", terminator: "");
}
main();
Output
Element : 7 33 28 23 0 2 9 35 13 42 1 3
Max Element : 42
Time Complexity
The time complexity of the algorithm can be analyzed based on the number of recursive calls made to find the maximum element. At each step, the problem is divided into two halves, resulting in a binary tree-like structure. The number of recursive calls made at each level of the binary tree is a power of 2 (as it splits the array in half).
Let n
be the number of elements in the array. The maximum depth of the recursion tree is log2(n)
,
as we divide the problem into two halves at each step. Therefore, the time complexity of the algorithm is
O(log n)
.
Resultant Output
For the given example array:
[7, 33, 28, 23, 0, 2, 9, 35, 13, 42, 1, 3]
The maximum element found using the recursive function is 42
.
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