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_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.

Categories
Relative Post