From: Robert Klemme <shortcutter@...>
Date: 2010-01-22T22:09:05+09:00
Subject: Re: Sorting Method

2010/1/22 Tim Pollard <slinkyabc@gmail.com>:
> Hi there,
>
> I am working my way through Chris Pine's Learn to Program, and am
> currently working on a sorting method (to ask the user for a list of
> words and then print them alphabetized.) He suggests that we write
> this program twice--once using recursion, and once using loops. I am
> currently working on the recursion program, which is the hard part for
> me; using loops doesn't really give me a problem.
>
> I guess the real root of my problem is my inability to understand
> methods and parameters. I also don't really understand the need to
> employ a wrapper...something else the book recommends. Obviously the
> book's recommendations have one-up on me, as Mr. Pine is able to write
> such a program and I am not. :)
>
> Here is the code I have right now, please tear it apart if necessary--
> I just really want to move forward but am nto willing to look up
> somebody else's method;  I think that what I am trying to do should
> work, it just...doesn't.
>
>  $input = ['']
>  $unsorted_array = []
>  $sorted_array = []
>
>    while not $input.empty?
>    $input = gets.chomp
>    $unsorted_array.push $input
>  end
>
> def recursive_sort
>      if $unsorted_array[0] < $unsorted_array[1]
>        $sorted_array.push && $unsorted_array.shift
>      else
>        $unsorted_array.push $unsorted_array[1] && $unsorted_array.shift
>      end
>    puts $sorted_array
> end
>
> recursive_sort

There is no recursion since recursive_sort does not call itself.

> I keep getting a number of errors, and changing things around...I was
> getting a stack overflow error for awhile, as well as an EXTREMELY
> frustrating "can't compare string to nil" error on the line comparing
> unsorted_array(0) to unsorted_array(1). I don't even know what I
> changed to make it go away--and the frustrating part is that I have no
> idea why my array contained a nil value in the first place...and as I
> was writing this I realized it must have been the ENTER that was
> returned as nil? That's all I can think of, but now when I run the
> program nothing happens at all. No errors, but no data output, either.
>
> I would greatly appreciate any insight somebody could offer on this.
> Thanks in advance!

If you have a recursive function (or method for that matter) you need
at least two branches in your function: one that steps into the
recursion and one that does not (terminates the recursion):

irb(main):001:0> def r_count(c) puts c; if c > 0; then r_count(c-1); end; end
=> nil
irb(main):002:0> r_count 5
5
4
3
2
1
0
=> nil
irb(main):003:0>

Otherwise you will see the stack overflow error that you have seen.

I don't know which recursive sorting algorithm you want to implement
but you could check here for explanations on some of them:

http://en.wikipedia.org/wiki/Sorting_algorithm

For general remarks about recursion

http://en.wikipedia.org/wiki/Recursion#Recursion_in_computer_science

Kind regards

robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/