The functional way to do "max" (with recursion / without mutable vars)

Question

Finding a max in an unsorted array with imperative code is quite straight forward

e.g. in Java (I'm sure it can be written better, only used for illustration purposes)

public class Main {
    public static void main(String[] args) {
        int[] array = {1,3,5,4,2};
        int max = findMax(array);
        System.out.println(max);
    }

    public static int findMax(int[] array){
        int max = Integer.MIN_VALUE; //or array[0], but it requires a null check and I want to keep it simple :)
        for (int i = 0, size = array.length; i < size ; i++) {
            int current = array[i];
            if(current > max) max = current;
        }
        return max;
    }
}

What is the functional way of doing it? e.g.

without mutable variables (e.g. make max be a val in Scala / final in Java)
without looping (e.g. use recursion, tail preferred)

In Scala's sources I saw it was done using recudeLeft, which seems quite clever

  def max[B >: A](implicit cmp: Ordering[B]): A = {
    if (isEmpty)
      throw new UnsupportedOperationException("empty.max")

    reduceLeft((x, y) => if (cmp.gteq(x, y)) x else y)
  }

But let's say I don't have (for some reason) reduce / reduceLeft available / implemented (And I don't want / can't implement it for some reason, i.e. I'm working with plain Java)

What is the "idiomatic" functional way to do a max without relying on other functional methods (e.g. how would I implement it in bare bones Java for example, but with the functional paradigm in mind)

Answers can be with any language (Java / Scala preferred though)

maba · Accepted Answer · 2013-04-22 21:43:48Z

4

This is a tail call recursion implementation with accumulator for the max value.

public class Main {

    public static void main(String[] args) {
        System.out.println(max(new int[]{6, 3, 9, 4}));
    }

    public static int max(int[] ints) {
        return max(ints, Integer.MIN_VALUE);
    }

    public static int max(int[] ints, int max) {
        if (ints.length == 0) {
            return max;
        } else {
            return max(Arrays.copyOfRange(ints, 1, ints.length), ints[0] > max ? ints[0] : max);
        }
    }

}

answered Apr 22, 2013 at 21:43

maba

48.3k10 gold badges114 silver badges119 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

ataylor Over a year ago

I would make the max of an empty list to be an error instead of Integer.MIN_VALUE, like in the Scala version with reduce.

maba Over a year ago

@ataylor I agree but this code snippet was more of an illustration than a production ready deliverable.

Eran Medan Over a year ago

Thanks! my eyes has been closed so far :) p.s. amazing how this is so much smaller in Scala (based on your answer):

def max(list: List[Int]) = {   	maxAcc(list, Int.MinValue)   }                                                    def maxAcc(list: List[Int], curMax:Int):Int = {   	list match {   		case Nil => curMax   		case head :: tail => maxAcc(tail, if (head > curMax ) head else curMax )   	}   }

maba Over a year ago

@Eran Don't forget to annotate with @tailrec in scala.

Eran Medan Over a year ago

Thanks, posted it as an answer if you don't mind in case someone will be interested

pt2121 · Accepted Answer · 2013-04-22 21:53:32Z

1

You can do it with a plain recursion but maba's tail recursion version should have a better performance.

import java.util.Arrays;
public class TestMax {
public static int findMax(int[] array) {
    if(array.length == 1)
        return array[0];
    int[] newArray = Arrays.copyOfRange(array, 1, array.length);
    if(array[0] > findMax(newArray))
        return array[0];
    else
        return findMax(newArray);
}
/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] array = {1,3,5,4,2, 9};
    int max = findMax(array);
    System.out.println(max);
}
}

answered Apr 22, 2013 at 21:53

pt2121

11.9k8 gold badges54 silver badges69 bronze badges

Comments

2 revs · Accepted Answer · 2013-04-22 22:31:15Z

Based on maba's excellent answer here is the Scala version if anyone was interested

  def max(list: List[Int]) = {
    maxAcc(list, Int.MinValue)
  }                                               

  def maxAcc(list: List[Int], curMax:Int):Int = {
    list match {
        case Nil => curMax
        case head :: tail => maxAcc(tail, if (head > curMax ) head else curMax )
    }
  }

Edit: thanks to maba's comment on @tailrec - here is the modified version

 def max(list: List[Int]) = {
    @tailrec def maxAcc(list: List[Int], curMax: Int): Int = {
      list match {
        case Nil => curMax
        case head :: tail => maxAcc(tail, if (head > curMax) head else curMax)
      }
    }
    maxAcc(list, Int.MinValue)
  }

Collectives™ on Stack Overflow

The functional way to do "max" (with recursion / without mutable vars)

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related