Skip to main content

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.

Last updated on by Kalkicode




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