CODEWITHSUNDEEP
scala
RDJ
RDJ

Reputation: 4122

Scala: Recursively find max of array

I'm new to scala. To practice recursion I set myself the task of finding the max value of an array. My base case is an array of length 1. For each recursive pass I'm comparing the sizes of the array values 0 and 1, eliminating the smaller value until the base case is met. 

  def max(m: Array[Int]): Int = {
      if (m.length == 1) m(0)
      else if (m(0) > m(1)) m.take(1)
      else m.take(0)
    return max(m)
  }

However in the repl this returns nothing (presumably an infinite loop). I don't understand why the array doesn't reduce to length 1. Do I need a secondary inner function or something?

Upvotes: 1

Views: 999

Answers (2)

Ray Toal
Ray Toal

Reputation: 88378

This is definitely an infinite loop, as you are recursively calling max with the same argument you passed in (in the lingo, take is not a modifier).

To answer the rest of the question, you do not need an inner helper function.

Try to translate the following algorithm to Scala:

  • If the list is empty, throw an error
  • Else if the list has one element return its first element
  • Else
    • (Recursively) compute the max of m.take(1), call this max_of_rest
    • Return the larger of m(0) and max_of_rest

Have fun learning recursion in Scala!

ADDENDUM

The above algorithm, while it produces the correct answer, does so inefficiently. Consider:

maximum([2, 4, 1, 10, 3])
  = max(2, maximum([4, 1, 10, 3]))
  = max(2, max(4, maximum([1, 10, 3])))
  = max(2, max(4, max(1, maximum([10, 3]))))
  = max(2, max(4, max(1, max(10, maximum([3])))))
  = max(2, max(4, max(1, max(10, 3))))
  = max(2, max(4, max(1, 10)))
  = max(2, max(4, 10))
  = max(2, 10)
  = 10

Note how each of calls "pile up" on the call stack, consuming lots of extra memory. It is much better in this case to use a tail-recursive formulation.

maximum([2, 4, 1, 10, 3])
  = _maximum([4, 1, 10, 3], max(4, 2))
  = _maximum([1, 10, 3], max(1, 4))
  = _maximum([10, 3], max(10, 4))
  = _maximum([3], max(3, 10))
  = _maximum([], 10)
  = 10

Now in this tail-recursive case, as pointed out by Joost den Boer, you do have a second function. You can see that this inner recursive function works like this

_maximum(a, v) =
  if a is empty return v
  else return _maximum(a.take(1), max(a(0), v))

The outer function goes something like

maximum(a) =
  if a is empty raise an error
  else return _maximum(a.take(1), a(0))

I'm purposely not using Scala syntax so you can enjoy working it out. Have fun!

Upvotes: 4

avysk
avysk

Reputation: 2035

m.take() does not modify m. As a result you are calling max(m) with the very same array as an argument over and over.

scala> val m = Array(1, 2, 3, 4, 5);
m: Array[Int] = Array(1, 2, 3, 4, 5)

scala> m.take(1)
res0: Array[Int] = Array(1)

scala> m
res1: Array[Int] = Array(1, 2, 3, 4, 5)

Also notice that take() does not do at all what you think it is doing.

scala> m.take(0)
res2: Array[Int] = Array()

scala> m.take(3)
res3: Array[Int] = Array(1, 2, 3)

Upvotes: 2

Related Questions