A question about recursive programming

concise!!!

On Dec 12, 2005, at 12:52 PM, Hank G. wrote:

max function by recursive function.

Thats not so bad.

def max_by_recursion(arr)
a1 = arr.dup
m = a1.shift
max_by_recursion1(m, a1)
end

def max_by_recursion1(current_max, arr)
return current_max if arr.length == 0
candidate = arr.shift
candidate > current_max ? max_by_recursion1(candidate, arr) :
max_by_recursion1(current_max, arr)
end

Of course in ruby we’d write

arr.inject { |max, curr| if curr > max then curr else max end }

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.

Quoting William J. [email protected]:

class Array
def tail
self[1…-1]
end
end

That’s awesome.

-mental