From: Johannes Friestad <johannes.friestad@...>
Date: 2005-12-13T17:27:06+09:00
Subject: Re: A question about recursive programming

> def recursive_max(an_array)
>   if (an_array.size < 2)
>     an_array.first
>   else
>     rest_max = recursive_max(an_array[1..-1])
>     an_array.first > rest_max ? an_array.first : rest_max
>   end
> end

If you are going to use it for anything serious, you don't want to
recurse by arr[1..-1], since it creates a new copy of the array for
every element you compare.
Instead, you can use optional parameters to pass the current index and
the best value so far:

def rec_max(arr, i=0, best=MIN_INT)
 if (arr.size < 2): arr.first
 elsif i==arr.length: best
 else rec_max(arr, i+1, arr[i]>best ? arr[i] : best)  end
end

MIN_INT is the minimum value of a fixnum, almost anything will be
larger. Saves a clumsy nil-test in the recursive call.
Of course, without tail recusion optimization in ruby, the stack grows
with one method call for each element you access. (Using a language
with tail recursion optimization, like Lisp, the stack is not used at
all.)
In my installation the stack bottoms out at 1200 levels, meaning that
the recursive max won't work if you need to compare more than 1200
elements.