Posted on by Kalkicode
Code Recursion

Find second largest element in an array using recursion

In this article, we will explore how to find the second largest element in an array using recursion. We'll begin by understanding the problem statement, then proceed with the explanation, a suitable example, pseudocode, algorithm, and finally, analyze the time complexity of the code.

Introduction

Finding the second largest element in an array is a common programming problem. Recursion is a technique where a function calls itself to solve smaller sub-problems, and it can be applied to find the second largest element in an array as well. The recursive approach allows us to break down the problem into smaller sub-problems and efficiently navigate through the array.

Problem Statement

Given an array of integers with more than two elements, we want to find the second largest element in the array. The array is not allowed to have all similar elements, meaning there must be at least two distinct elements to find a second largest.

Explanation

To find the second largest element in the array using recursion, we'll define a recursive function that will take the array, its size, and pointers to two variables to store the first and second largest elements. The recursive function will compare elements of the array and update the first and second largest accordingly until the end of the array is reached.

Example

Let's illustrate the process with an example. Consider the array: [10, 3, 23, 86, 8, 31, 9, 48, 5, 7]. Initially, the first and second largest variables are set to the first element (10) and negative infinity, respectively. The recursion will then traverse through the array and update the first and second largest values accordingly.

Pseudocode

The pseudocode for finding the second largest element using recursion is as follows:

function second_largest(arr, location, first, second):
    if location < 0:
        return
    else:
        if arr[location] > first:
            second = first
            first = arr[location]
        else if arr[location] > second:
            second = arr[location]
        second_largest(arr, location - 1, first, second)

function find_largest(arr, size):
    if size <= 0:
        return
    first = arr[0]
    second = -∞
    second_largest(arr, size - 1, first, second)
    print("Second largest:", second)

Algorithm

  1. Start the main function find_largest(arr, size).
  2. Check if the array size size is less than or equal to 0. If so, return, as it is not possible to find the second largest with less than two elements.
  3. Initialize two variables first and second to store the first and second largest elements, respectively. Set first to the first element of the array, and second to negative infinity.
  4. Call the recursive function second_largest(arr, size - 1, first, second), passing the array, one less than the size, first, and second as arguments.
  5. The recursive function second_largest(arr, location, first, second) will check if the current location in the array is less than 0. If so, return to stop the recursion.
  6. Compare the array element at the current location with the current first and second largest elements.
  7. If the array element is greater than first, update second with the current value of first and set first to the array element.
  8. If the array element is not greater than first but greater than second, update second with the array element.
  9. Call the recursive function second_largest(arr, location - 1, first, second) with the location one step back in the array.

Code Solution

Here given code implementation process.

//C Program 
//Find second largest element in an array using recursion
#include <stdio.h>

#include <limits.h>

//Find the second largest element in array
//Assume that array contains more than 2 elements and 
//Array is not contain all similar element
void second_largest(int arr[], int location, int *first, int *second)
{
	if (location < 0)
	{
		//Condition which is controlling the process of recursion
		return;
	}
	else
	{
		//Check whether given location array element is greater than of first largest element or not
		if ( *first < arr[location])
		{
			if ( *second < *first)
			{
				//When previous is a second largest element
				*second = *first;
			}
			//When get a new largest element
			*first = arr[location];
		}
		else if ( *second < arr[location])
		{
			//When get a new second largest element
			*second = arr[location];
		}
		//Recursive execute process
		second_largest(arr, location - 1, first, second);
	}
}
//This is handling the process of to find the second largest element in array
void find_largest(int arr[], int size)
{
	if (size <= 0)
	{
		return;
	}
	//Define two variable which is storing the information of 
	// first and second largest element
	// Get first element of array
	int first = arr[0];
	int second = INT_MIN;
	second_largest(arr, size - 1, & first, & second);
	//Display result
	printf("Second largest : %d\n", second);
}
int main()
{
	//Define collection of array elements
	int arr[] = {
		10 , 3 , 23 , 86 , 8 , 31 , 9 , 48 , 5 , 7
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	find_largest(arr, size);
	return 0;
}

Output

Second largest : 48
// Java Program
// Find second largest element in an array using recursion
class MyArray
{
	public int first;
	public int second;
	public MyArray()
	{
		this.first = 0;
		this.second = 0;
	}
	//Find the second largest element in array
	//Assume that array contains more than 2 elements and 
	//Array is not contain all similar element
	public void second_largest(int[] arr, int location)
	{
		if (location < 0)
		{
			//Condition which is controlling the process of recursion
			return;
		}
		else
		{
			//Check whether given location array element is greater than of first largest element or not
			if (this.first < arr[location])
			{
				if (this.second < this.first)
				{
					//When previous is a second largest element
					this.second = this.first;
				}
				//When get a new largest element
				this.first = arr[location];
			}
			else if (this.second < arr[location])
			{
				//When get a new second largest element
				this.second = arr[location];
			}
			//Recursive execute process
			second_largest(arr, location - 1);
		}
	}
	//This is handling the process of to find the second largest element in array
	public void find_largest(int[] arr, int size)
	{
		if (size <= 0)
		{
			return;
		}
		//Define two variable which is storing the information of 
		// first and second largest element
		// Get first element of array
		this.first = arr[0];
		this.second = Integer.MIN_VALUE;
		second_largest(arr, size - 1);
		System.out.print("Second largest : " + second + "\n");
	}
	public static void main(String[] args)
	{
		MyArray obj = new MyArray();
		//Define collection of array elements
		int[] arr = {
			10 , 3 , 23 , 86 , 8 , 31 , 9 , 48 , 5 , 7
		};
		//Get the size of array
		int size = arr.length;
		obj.find_largest(arr, size);
	}
}

Output

Second largest : 48
//Include header file
#include <iostream>

#include<limits.h>

using namespace std;
// C++ Program
// Find second largest element in an array using recursion
class MyArray
{
	public: int first;
	int second;
	MyArray()
	{
		this->first = 0;
		this->second = 0;
	}
	//Find the second largest element in array
	//Assume that array contains more than 2 elements and 
	//Array is not contain all similar element
	void second_largest(int arr[], int location)
	{
		if (location < 0)
		{
			//Condition which is controlling the process of recursion
			return;
		}
		else
		{
			//Check whether given location array element is greater than of first largest element or not
			if (this->first < arr[location])
			{
				if (this->second < this->first)
				{
					//When previous is a second largest element
					this->second = this->first;
				}
				//When get a new largest element
				this->first = arr[location];
			}
			else if (this->second < arr[location])
			{
				//When get a new second largest element
				this->second = arr[location];
			}
			//Recursive execute process
			this->second_largest(arr, location - 1);
		}
	}
	//This is handling the process of to find the second largest element in array
	void find_largest(int arr[], int size)
	{
		if (size <= 0)
		{
			return;
		}
		//Define two variable which is storing the information of 
		// first and second largest element
		// Get first element of array
		this->first = arr[0];
		this->second = INT_MIN;
		this->second_largest(arr, size - 1);
		cout << "Second largest : " << this->second << "\n";
	}
};
int main()
{
	MyArray obj = MyArray();
	int arr[] = {
		10 , 3 , 23 , 86 , 8 , 31 , 9 , 48 , 5 , 7
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	obj.find_largest(arr, size);
	return 0;
}

Output

Second largest : 48
//Include namespace system
using System;

// C# Program
// Find second largest element in an array using recursion
class MyArray
{
	public int first;
	public int second;
	public MyArray()
	{
		this.first = 0;
		this.second = 0;
	}
	//Find the second largest element in array
	//Assume that array contains more than 2 elements and 
	//Array is not contain all similar element
	public void second_largest(int[] arr, int location)
	{
		if (location < 0)
		{
			//Condition which is controlling the process of recursion
			return;
		}
		else
		{
			//Check whether given location array element is greater than of first largest element or not
			if (this.first < arr[location])
			{
				if (this.second < this.first)
				{
					//When previous is a second largest element
					this.second = this.first;
				}
				//When get a new largest element
				this.first = arr[location];
			}
			else if (this.second < arr[location])
			{
				//When get a new second largest element
				this.second = arr[location];
			}
			//Recursive execute process
			second_largest(arr, location - 1);
		}
	}
	//This is handling the process of to find the second largest element in array
	public void find_largest(int[] arr, int size)
	{
		if (size <= 0)
		{
			return;
		}
		//Define two variable which is storing the information of 
		// first and second largest element
		// Get first element of array
		this.first = arr[0];
		this.second = int.MinValue;
		second_largest(arr, size - 1);
		Console.Write("Second largest : " + second + "\n");
	}
	public static void Main(String[] args)
	{
		MyArray obj = new MyArray();
		int[] arr = {
			10 , 3 , 23 , 86 , 8 , 31 , 9 , 48 , 5 , 7
		};
		//Get the size of array
		int size = arr.Length;
		obj.find_largest(arr, size);
	}
}

Output

Second largest : 48
<?php
// Php Program
// Find second largest element in an array using recursion
class MyArray
{
	public $first;
	public $second;

	function __construct()
	{
		$this->first = 0;
		$this->second = 0;
	}
	//Find the second largest element in array
	//Assume that array contains more than 2 elements and 
	//Array is not contain all similar element
	public	function second_largest( & $arr, $location)
	{
		if ($location < 0)
		{
			//Condition which is controlling the process of recursion
			return;
		}
		else
		{
			//Check whether given location array element is greater than of first largest element or not
			if ($this->first < $arr[$location])
			{
				if ($this->second < $this->first)
				{
					//When previous is a second largest element
					$this->second = $this->first;
				}
				//When get a new largest element
				$this->first = $arr[$location];
			}
			else if ($this->second < $arr[$location])
			{
				//When get a new second largest element
				$this->second = $arr[$location];
			}
			//Recursive execute process
			$this->second_largest($arr, $location - 1);
		}
	}
	//This is handling the process of to find the second largest element in array
	public	function find_largest( & $arr, $size)
	{
		if ($size <= 0)
		{
			return;
		}
		//Define two variable which is storing the information of 
		// first and second largest element
		// Get first element of array
		$this->first = $arr[0];
		$this->second = -PHP_INT_MAX;
		$this->second_largest($arr, $size - 1);
		echo "Second largest : ". $this->second ."\n";
	}
}

function main()
{
	$obj = new MyArray();
	//Define collection of array elements
	$arr = array(10, 3, 23, 86, 8, 31, 9, 48, 5, 7);
	//Get the size of array
	$size = count($arr);
	$obj->find_largest($arr, $size);
}
main();

Output

Second largest : 48
// Node Js Program
// Find second largest element in an array using recursion
class MyArray
{
	constructor()
	{
		this.first = 0;
		this.second = 0;
	}
	//Find the second largest element in array
	//Assume that array contains more than 2 elements and 
	//Array is not contain all similar element
	second_largest(arr, location)
	{
		if (location < 0)
		{
			//Condition which is controlling the process of recursion
			return;
		}
		else
		{
			//Check whether given location array element is greater than of first largest element or not
			if (this.first < arr[location])
			{
				if (this.second < this.first)
				{
					//When previous is a second largest element
					this.second = this.first;
				}
				//When get a new largest element
				this.first = arr[location];
			}
			else if (this.second < arr[location])
			{
				//When get a new second largest element
				this.second = arr[location];
			}
			//Recursive execute process
			this.second_largest(arr, location - 1);
		}
	}
	//This is handling the process of to find the second largest element in array
	find_largest(arr, size)
	{
		if (size <= 0)
		{
			return;
		}
		//Define two variable which is storing the information of 
		// first and second largest element
		// Get first element of array
		this.first = arr[0];
		this.second = -Number.MAX_VALUE;
		this.second_largest(arr, size - 1);
		process.stdout.write("Second largest : " + this.second + "\n");
	}
}

function main()
{
	var obj = new MyArray();
	//Define collection of array elements
	var arr = [10, 3, 23, 86, 8, 31, 9, 48, 5, 7];
	//Get the size of array
	var size = arr.length;
	obj.find_largest(arr, size);
}
main();

Output

Second largest : 48
import sys

#  Python 3 Program
#  Find second largest element in an array using recursion
class MyArray :
	
	def __init__(self) :
		self.first = 0
		self.second = 0
	
	# Find the second largest element in array
	# Assume that array contains more than 2 elements and 
	# Array is not contain all similar element
	def second_largest(self, arr, location) :
		if (location < 0) :
			# Condition which is controlling the process of recursion
			return
		else :
			# Check whether given location array element is greater than of first largest element or not
			if (self.first < arr[location]) :
				if (self.second < self.first) :
					# When previous is a second largest element
					self.second = self.first
				
				# When get a new largest element
				self.first = arr[location]
			
			elif(self.second < arr[location]) :
				# When get a new second largest element
				self.second = arr[location]
			
			# Recursive execute process
			self.second_largest(arr, location - 1)
		
	
	# This is handling the process of to find the second largest element in array
	def find_largest(self, arr, size) :
		if (size <= 0) :
			return
		
		# Define two variable which is storing the information of 
		#  first and second largest element
		#  Get first element of array
		self.first = arr[0]
		self.second = -sys.maxsize
		self.second_largest(arr, size - 1)
		print("Second largest : ", self.second ,"\n", end = "")
	

def main() :
	obj = MyArray()
	# Define collection of array elements
	arr = [10, 3, 23, 86, 8, 31, 9, 48, 5, 7]
	# Get the size of array
	size = len(arr)
	obj.find_largest(arr, size)

if __name__ == "__main__": main()

Output

Second largest :  48
#  Ruby Program
#  Find second largest element in an array using recursion
class MyArray 

	# Define the accessor and reader of class MyArray  
	attr_reader :first, :second
	attr_accessor :first, :second

	def initialize()
		self.first = 0
		self.second = 0
	end
	# Find the second largest element in array
	# Assume that array contains more than 2 elements and 
	# Array is not contain all similar element
	def second_largest(arr, location)
	
		if (location < 0)
		
			# Condition which is controlling the process of recursion
			return
		else
		
			# Check whether given location array element is greater than of first largest element or not
			if (self.first < arr[location])
			
				if (self.second < self.first)
				
					# When previous is a second largest element
					self.second = self.first
				end
				# When get a new largest element
				self.first = arr[location]
			elsif(self.second < arr[location])
			
				# When get a new second largest element
				self.second = arr[location]
			end
			# Recursive execute process
			self.second_largest(arr, location - 1)
		end
	end
	# This is handling the process of to find the second largest element in array
	def find_largest(arr, size)
	
		if (size <= 0)
		
			return
		end
		# Define two variable which is storing the information of 
		#  first and second largest element
		#  Get first element of array
		self.first = arr[0]
		self.second = -(2 ** (0. size * 8 - 2))
		self.second_largest(arr, size - 1)
		print("Second largest : ", @second ,"\n")
	end
end
def main()

	obj = MyArray.new()
	# Define collection of array elements
	arr = [10, 3, 23, 86, 8, 31, 9, 48, 5, 7]
	# Get the size of array
	size = arr.length
	obj.find_largest(arr, size)
end
main()

Output

Second largest : 48
// Scala Program
// Find second largest element in an array using recursion
class MyArray(var first: Int,
	var second: Int)
{
	def this()
	{
		this(0, 0);
	}
	//Find the second largest element in array
	//Assume that array contains more than 2 elements and 
	//Array is not contain all similar element
	def second_largest(arr: Array[Int], location: Int): Unit = {
		if (location < 0)
		{
			//Condition which is controlling the process of recursion
			return;
		}
		else
		{
			//Check whether given location array element is greater than of first largest element or not
			if (this.first < arr(location))
			{
				if (this.second < this.first)
				{
					//When previous is a second largest element
					this.second = this.first;
				}
				//When get a new largest element
				this.first = arr(location);
			}
			else if (this.second < arr(location))
			{
				//When get a new second largest element
				this.second = arr(location);
			}
			//Recursive execute process
			second_largest(arr, location - 1);
		}
	}
	//This is handling the process of to find the second largest element in array
	def find_largest(arr: Array[Int], size: Int): Unit = {
		if (size <= 0)
		{
			return;
		}
		//Define two variable which is storing the information of 
		// first and second largest element
		// Get first element of array
		this.first = arr(0);
		this.second = Int.MinValue;
		second_largest(arr, size - 1);
		print("Second largest : " + second + "\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyArray = new MyArray();
		//Define collection of array elements
		var arr: Array[Int] = Array(10, 3, 23, 86, 8, 31, 9, 48, 5, 7);
		//Get the size of array
		var size: Int = arr.length;
		obj.find_largest(arr, size);
	}
}

Output

Second largest : 48
// Swift Program
// Find second largest element in an array using recursion
class MyArray
{
	var first: Int;
	var second: Int;
	init()
	{
		self.first = 0;
		self.second = 0;
	}
	//Find the second largest element in array
	//Assume that array contains more than 2 elements and 
	//Array is not contain all similar element
	func second_largest(_ arr: [Int], _ location: Int)
	{
		if (location < 0)
		{
			//Condition which is controlling the process of recursion
			return;
		}
		else
		{
			//Check whether given location array element is greater than of first largest element or not
			if (self.first < arr[location])
			{
				if (self.second < self.first)
				{
					//When previous is a second largest element
					self.second = self.first;
				}
				//When get a new largest element
				self.first = arr[location];
			}
			else if (self.second < arr[location])
			{
				//When get a new second largest element
				self.second = arr[location];
			}
			//Recursive execute process
			self.second_largest(arr, location - 1);
		}
	}
	//This is handling the process of to find the second largest element in array
	func find_largest(_ arr: [Int], _ size: Int)
	{
		if (size <= 0)
		{
			return;
		}
		//Define two variable which is storing the information of 
		// first and second largest element
		// Get first element of array
		self.first = arr[0];
		self.second = Int.min;
		self.second_largest(arr, size - 1);
		print("Second largest : ", self.second ,"\n", terminator: "");
	}
}
func main()
{
	let obj: MyArray = MyArray();
	//Define collection of array elements
	let arr: [Int] = [10, 3, 23, 86, 8, 31, 9, 48, 5, 7];
	//Get the size of array
	let size: Int = arr.count;
	obj.find_largest(arr, size);
}
main();

Output

Second largest :  48

Resultant Output

For the given example array [10, 3, 23, 86, 8, 31, 9, 48, 5, 7], the output will be: "Second largest: 48".

Time Complexity Analysis

The time complexity of the recursive approach to finding the second largest element in an array can be expressed as O(n), where n is the number of elements in the array. This is because the recursion iterates through each element once, making it a linear time complexity. The recursive call is made n times, but each call only processes one element, and the total number of comparisons is proportional to the number of elements, resulting in O(n) time complexity. The space complexity of the algorithm is O(1) as we are not using any additional data structures with respect to the input size.

In conclusion, we have explored how to find the second largest element in an array using recursion. We learned how to approach the problem, provided a suitable example, explained the pseudocode and algorithm, and analyzed the time complexity of the code. The recursive approach is an elegant solution to this problem, allowing us to efficiently find the second largest element in the array with a time complexity of O(n).

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