Simple demonstration of potential elegance of recursion.

ruby_recursion.rb

#/usr/bin/env ruby


# Naive binary search tree implementation, but illustrates my point
# that one of the key elegances of recursive algorithms
# is that the 'shape' of the code closely matches the 'shape'
# of the data.
# 
# So the definition of a binary search tree is either 
# a) it's empty (nil in the ruby example)
# b) it's a node with 
#         a binary search tree with smaller numbers to its left
#         and a binary search tree with larger numbers to its right
#   

def new_bst_inserting_node(tree,index,name)
  case
    when tree.nil?
      node(index,name,nil,nil)
    
    when (index < tree[:index])
      node(tree[:index],
            tree[:name],
            new_bst_inserting_node(tree[:left],index,name),
            tree[:right])
            
    when (index > tree[:index])
      node(tree[:index],
           tree[:name],
           tree[:left],
           new_bst_inserting_node(tree[:right],index,name))
    end
end

def bst_include?(tree,index)
  case 
    when tree.nil?
      false
    when (index == tree[:index])
      true
    when (index < tree[:index])
      bst_include?(tree[:left],index)
    when (index > tree[:index])
      bst_include?(tree[:right],index)
    end
end

# You wouldn't normally iterate arrays like this in ruby
# but I wanted to illustrate that you can also define arrays
# recursively as either
#   a) empty
#   b) the first element in the array, and another array made from the rest of it
# This might be a common idiom in languages like the LISP family but unlike
# trees I don't tend to think of arrays as naturally recursive structures.

def create_bst_from_array(array)
    return nil if array.empty?

    first, *rest = array
    new_bst_inserting_node(
     create_bst_from_array(rest), # RECURSE!!!
     first[0], first)
end

def node(index,name,left,right)
  {:index => index, :name=> name, 
    :left=> left, :right => right}
end

array = "the quick brown fox jumps over lazy dogs".split

require 'yaml'
puts create_bst_from_array(array).to_yaml

## And here's another recursive array algo. Remove duplicates from
## a sorted array - this makes more sense than the one above

array = [ 'a','a', 'b', 'b','c','d','e','e','f']

def remove_dupes(array)
  first, *rest = array
  
  case
  when array.empty?
    []
  when rest.empty?
    first
  when (first == rest.first)
    remove_dupes(rest) 
  else
    [first, *remove_dupes(rest)]
  end
end

puts remove_dupes(array).inspect