How to find the largest element in a list of integers recursively?

scala max(list recursive)
find largest number in array using recursion java
c program to find maximum and minimum number in an array using recursion
find the smallest number in an array using recursion in c
recursive max function python
scala max int
scala program to find second maximum number of four given numbers
scala find minimum in list

I'm trying to write a function which will recursively find the largest element in a list of integers. I know how to do this in Java, but can't understand how to do this at Scala.

Here is what I have so far, but without recursion:

  def max(xs: List[Int]): Int = {
    if (xs.isEmpty) throw new java.util.NoSuchElementException();
    else xs.max;
  }

How can we find it recursively with Scala semantic.

This is the most minimal recursive implementation of max I've ever been able to think up:

def max(xs: List[Int]): Option[Int] = xs match {
  case Nil => None
  case List(x: Int) => Some(x)
  case x :: y :: rest => max( (if (x > y) x else y) :: rest )
} 

It works by comparing the first two elements on the list, discarding the smaller (or the first, if both are equal) and then calling itself on the remaining list. Eventually, this will reduce the list to one element which must be the largest.

I return an Option to deal with the case of being given an empty list without throwing an exception - which forces the calling code to recognise the possibility and deal with it (up to the caller if they want to throw an exception).

If you want it to be more generic, it should be written like this:

def max[A <% Ordered[A]](xs: List[A]): Option[A] = xs match {
  case Nil => None
  case x :: Nil => Some(x)
  case x :: y :: rest => max( (if (x > y) x else y) :: rest )
}

Which will work with any type which either extends the Ordered trait or for which there is an implicit conversion from A to Ordered[A] in scope. So by default it works for Int, BigInt, Char, String and so on, because scala.Predef defines conversions for them.

We can become yet more generic like this:

def max[A <% Ordered[A]](xs: Seq[A]): Option[A] = xs match {
  case s if s.isEmpty || !s.hasDefiniteSize => None
  case s if s.size == 1 => Some(s(0))
  case s if s(0) <= s(1) => max(s drop 1)
  case s => max((s drop 1).updated(0, s(0)))
}

Which will work not just with lists but vectors and any other collection which extends the Seq trait. Note that I had to add a check to see if the sequence actually has a definite size - it might be an infinite stream, so we back away if that might be the case. If you are sure your stream will have a definite size, you can always force it before calling this function - it's going to work through the whole stream anyway. See notes at the end for why I really would not want to return None for an indefinite stream, though. I'm doing it here purely for simplicity.

But this doesn't work for sets and maps. What to do? The next common supertype is Iterable, but that doesn't support updated or anything equivalent. Anything we construct might be very poorly performing for the actual type. So my clean no-helper-function recursion breaks down. We could change to using a helper function but there are plenty of examples in the other answers and I'm going to stick with a one-simple-function approach. So at this point, we can to switch to reduceLeft (and while we are at it, let's go for `Traversable' and cater for all collections):

def max[A <% Ordered[A]](xs: Traversable[A]): Option[A] = {
  if (xs.hasDefiniteSize) 
    xs reduceLeftOption({(b, a) => if (a >= b) a else b}) 
  else None
}

but if you don't consider reduceLeft recursive, we can do this:

def max[A <% Ordered[A]](xs: Traversable[A]): Option[A] = xs match {
  case i if i.isEmpty => None
  case i if i.size == 1 => Some(i.head)
  case i if (i collect { case x if x > i.head => x }).isEmpty => Some(i.head)
  case _ => max(xs collect { case x if x > xs.head => x })
}

It uses the collect combinator to avoid some clumsy method of bodging a new Iterator out of xs.head and xs drop 2.

Either of these will work safely with almost any collection of anything which has an order. Examples:

scala>  max(Map(1 -> "two", 3 -> "Nine", 8 -> "carrot"))
res1: Option[(Int, String)] = Some((8,carrot))

scala> max("Supercalifragilisticexpialidocious")
res2: Option[Char] = Some(x)

I don't usually give these others as examples, because it requires more expert knowledge of Scala.

Also, do remember that the basic Traversable trait provides a max method, so this is all just for practice ;)

Note: I hope that all my examples show how careful choice of the sequence of your case expressions can make each individual case expression as simple as possible.

More Important Note: Oh, also, while I am intensely comfortable returning None for an input of Nil, in practice I'd be strongly inclined to throw an exception for hasDefiniteSize == false. Firstly, a finite stream could have a definite or non-definite size dependent purely on the sequence of evaluation and this function would effectively randomly return Option in those cases - which could take a long time to track down. Secondly, I would want people to be able to differentiate between having passed Nil and having passed truly risk input (that is, an infinite stream). I only returned Option in these demonstrations to keep the code as simple as possible.

Recursive Programs to find Minimum and Maximum elements of array, Given an array of integers arr, the task is to find the minimum and maximum element of that array using recursion. Examples : Input: arr = {1, 4, 3, -5, -4, 8, 6};​  Recursively find the maximum according to the following: Recursively traverse the array from the end Base case: If the remaining array is of length 1, return the only present element i.e. arr[0]

The easiest approach would be to use max function of TraversableOnce trait, as follows,

val list = (1 to 10).toList
list.max

to guard against the emptiness you can do something like this,

if(list.empty) None else Some(list.max)

Above will give you an Option[Int]

My second approach would be using foldLeft

(list foldLeft None)((o, i) => o.fold(Some(i))(j => Some(Math.max(i, j))))

or if you know a default value to be returned in case of empty list, this will become more simpler.

val default = 0
(list foldLeft default)(Math.max)

Anyway since your requirement is to do it in recursive manner, I propose following,

def recur(list:List[Int], i:Option[Int] = None):Option[Int] = list match {
  case Nil => i
  case x :: xs => recur(xs, i.fold(Some(x))(j => Some(Math.max(j, x))))
}

or as default case,

val default = 0
def recur(list:List[Int], i:Int = default):Int = list match {
  case Nil => i
  case x :: xs => recur(xs, i.fold(x)(j => Math.max(j, x)))
}

Note that, this is tail recursive. Therefore stack is also saved.

How to find the largest element in a list of integers recursively?, Here is what I have so far, but without recursion: def max(xs: List[Int]): Int = { if (xs NoSuchElementException(); else xs.max; } How can we find it recursively with​  Write C and Java programs to find the largest element in an array using recursion. Here, we develop C and Java code to find the maximum element in an array using recursion. We develop a method revursiveMax that takes an array arr storing n integers, where n >= 1 and returns the maximum element in arr.

If you want functional approach to this problem then use reduceLeft:

def max(xs: List[Int]) = {
  if (xs.isEmpty) throw new NoSuchElementException
  xs.reduceLeft((x, y) => if (x > y) x else y)
}

This function specific for list of ints, if you need more general approach then use Ordering typeclass:

def max[A](xs: List[A])(implicit cmp: Ordering[A]): A = {
  if (xs.isEmpty) throw new NoSuchElementException
  xs.reduceLeft((x, y) => if (cmp.gteq(x, y)) x else y)
}   

reduceLeft is a higher-order function, which takes a function of type (A, A) => A, it this case it takes two ints, compares them and returns the bigger one.

C Program to find the Largest Array Element Using Recursion, C Program to find the largest Element in an Array using Recursion #define MAX 100 int getMaxElement(int []); // takes array of int as parameter int size; int  Now the second largest must have, at some point, been compared to the largest or it wouldn't have been eliminated. Log n is the number of elements that were compared to the largest, so we have only to find the largest of a set with log n elements.

You could use pattern matching like that

def max(xs: List[Int]): Int = xs match {
  case Nil => throw new NoSuchElementException("The list is empty")
  case x :: Nil => x
  case x :: tail => x.max(max(tail)) //x.max is Integer's class method
}

All About Recursion, The factorial of a positive integer n, written n!, is the product of all the positive integers from 1 up to and including n. def maximum(numbers): "Returns the largest number in a list. We will use recursion to find the maximum value in an array. I need to use recursion to find the largest int in an array. What I have so far is. #include <iostream> using std::cout; using std::endl; int maxArray(int anArray[], int size); /** *The main method * *@param myArray[] The array we are searching * *@param sizeOfArray The size of the array * *@param largestNumber The largest number in the array */ int main(){ int myArray[] = { 1, 6, 8, 3 }; int

Scala is a functional language whereby one is encourage to think recursively. My solution as below. I recur it base on your given method.

  def max(xs: List[Int]): Int = {
    if(xs.isEmpty == true) 0
    else{
      val maxVal= max(xs.tail)
      if(maxVal >= xs.head) maxVal 
      else                  xs.head     
    }
  }

Updated my solution to tail recursive thanks to suggestions.

  def max(xs: List[Int]): Int = {    
    def _max(xs: List[Int], maxNum: Int): Int = {   
      if (xs.isEmpty) maxNum
      else {
        val max = {
          if (maxNum >= xs.head) maxNum
          else xs.head
        }
        _max(xs.tail, max)
      }
    }
    _max(xs.tail, xs.head)
  }

Intro-to-Java-Programming/Exercise_18_13.java at master , (Find the largest number in an array) Write a recursive method that returns *. * the largest enter a list of eight integers and displays the largest element. *. At each element, you return the larger of the current element, and all of the elements with a greater index. Integer.MIN_VALUE will be returned only on empty arrays. This runs in linear time.

C Program to Find the Biggest Number in an Array of Numbers using , C Program to find the Biggest Number in an Array of Numbers using; * Recursion; */; #include <stdio.h>; int large(int[], int, int);; int main(); {; int size;; int largest; The solution you have provided for the first question is not recursive. You can have a recursion that will stop when max.next() is null, and otherwise will return the max value between the current node and the next node.

[PDF] OCaml: Fold, with Tail Recursion Review, h :: t -> h +. sum_list t. To find the max of a positive int list, we recursively walk over the list and keep track of the greatest element: let rec max_list l = match l with. In the non-recursive case (where len(l) == 1), you should return l[0] (the minimum of a list with one element is that one element). Then, it is correct to call findMinimum inside your function again (that's the recursive call, as you know); however, what you probably want is to call it with the all the list l except the first element, that is

Scala Recursion – Get the Sum and Max in a List – Glyphex, * This is an auxiliary method use to get the largest number. */. def max(xs : List[Int]​, i :  Given an array of integers, find sum of array elements using recursion. Examples: Input : A[] = {1, 2, 3} Output : 6 1 + 2 + 3 = 6 Input : A[] = {15, 12, 13, 10} Output : 50. We have discussed iterative solution in below post. Sum of elements in a given array. In this post, recursive solution is discussed.

Comments
  • Do you consider the fold and reduce methods to be recursive? They are in a mathematical sense.
  • you can use x.max(y) instead of the if-else
  • @Chirlo no, I cannot and I would not. Did you notice that my code is as generic as possible? I cannot because the Ordered trait does not define any such method. Hell, Int doesn't either, but RichInt does, so an implicit conversion takes care of that. I would not, in any case, because it could cause confusion to the reader (or error by the coder) inside a function which is itself called max
  • I meant on your first example in which you do use Int , guess I should have been clearer.
  • No problem. Yes, I could. No, I wouldn't. ;)
  • Like your first approach. Since it is definetly the easiest one, is there any reason why recursion would be better (beside that the question asked for recursion)?
  • Not that I can think of. We used to write the recursion functions for that kind of simple applications when we are learning the scala.
  • Use reduceLeftOption and let the caller decide what to do if an empty list was passed. It might not be a problem for their code.
  • @itsbruce i don't think that using Option as a result type in such function is a good design.
  • Why not? Option is a very Scala way of doing something; the signature signals to the caller that there may be a problem but it leaves them the choice of how to deal with it. It also allows creative use of for comprehensions and Monadic solutions. Throwing an exception forces the caller to wrap your function in a try/call block if they want do do anything elegant. Option is much more composable.
  • @itsbruce The problem is that it should not signal, max is a primitive operation which should not force the developer to use Option all over the code. That's the idea of combinators library, if the developer wants to use Option if the list is empty then, according to FP way, he should combine a function which checks for list emptiness and wraps the result to None/Some and a primitive function
  • If I were extending the collections combinator code, I'd provide max and maxOption because that matches the style there, but this is a standalone function. You could call it a question of style, but I prefer to default to the functional style; imperative coders will always find ways to make it imperative, without any help.
  • if (xs.isEmpty == true) comparing boolean with boolean is useless in if you can just write if (xs.isEmpty)