Recursion in Ruby

Studying Ruby and object oriented programming at Dev Bootcamp we have been working with exercises that lend themselves to recursive thinking. Because recursion was challenging yet often elegant I researched the subject further in the context of the Ruby language. For more here is an excellent resource on recursion in Ruby by Jean-Denis Vauguet.

What is Recursion?

Recursion is a method of solving problems by dividing them into the same problem of a smaller size. A recursive method calls itself a certain number of times. It is commonly found in functional languages however imperative languages such as Ruby can make use of recursive algorithms.

Perhaps surprisingly all iterations can be written recursively. Loops that rely on while or until are often intuitive candidates. The while or until loop condition can often be coerced into a recursive base case.

The Base Case

The key to recursion is limiting the number of method self-calls. To limit the number of calls we must establish a base case. When the base case has been reached the method stops calling itself and begins returning up the chain of method calls.

Considerations for Recursion in Ruby

Recursion in Ruby and most imperative languages is considered inefficient. Because almost everything is an object in Ruby, repeated object instantiation can arise in recursive calls, leading to reduced speed. Furthermore additional stack frames are required for each method call's arguments and local variables. Too many recursive calls can lead to stack overflow induced crashes. Tail Call Recursion and Memoization can help reduce the risk of stack overflow.

Tail Call Optimization

Tail Call Optimization allows recursive method calls without the allocation of additional memory on the stack. Simply put the calling method returns the value it gets from the called method. Therefore recursive methods are implemented in constant stack space eliminating the risk of stack overflow.

Memoization

Memoization of a method eliminates repeat calculations of results for prior inputs. A memoized method has a lookup table of prior inputs and outputs that it can use to speed up future calls for new inputs. With the added lookup table, memoization lowers a method's time cost at the expense of added space cost. If methods are well-defined, i.e. they consistently return the same output for given arguments, then this can be an effective tool to reduce the risk of stack overflow.

Boggle: Recursion Example

Below is a program the generates a random boggle board. It then takes a string from the user and returns true if the string is made of sequentially adjacent dice, whether they are horizontally, diagonally, or vertically neighboring. Using recursion, BoggleBoard#include? takes the first letter of the user's string and then traverses all possible paths from the occurrences of the letter on the board looking for a match.

class BoggleBoard

  attr_accessor :board

  DICE = [
          ["A", "A", "E", "E", "G", "N"],
          ["A", "B", "B", "J", "O", "O"],
          ["A", "C", "H", "O", "P", "S"],
          ["A", "F", "F", "K", "P", "S"],
          ["A", "O", "O", "T", "T", "W"],
          ["C", "I", "M", "O", "T", "V"],
          ["D", "E", "I", "L", "R", "X"],
          ["H", "L", "N", "N", "R", "Z"],
          ["D", "I", "S", "T", "T", "Y"],
          ["E", "E", "G", "H", "N", "W"],
          ["E", "E", "I", "N", "S", "U"],
          ["E", "H", "R", "T", "V", "W"],
          ["E", "I", "O", "S", "S", "T"],
          ["E", "L", "R", "T", "T", "Y"],
          ["H", "A", "E", "E", "G", "N"],
          ["A", "I", "M", "N", "Q", "U"]
        ]

  def initialize
    @board = []
    @shake_counter = 0
  end

  def shake!
    @board = []

    DICE.each do |die|
      @board << Node.new(die.sample)
    end

    @shake_counter += 1
    populate_neighbors
    display

  end

  def display
    @board.each_slice(4) do |slice|
      slice.each do |node|
        print node.value
      end
      puts ""
   end
  end

  # Generate neighbors for each dice in the board.
  def populate_neighbors
    @board.each_with_index do |node, node_index|
      node.neighbors << @board[node_index + 1] unless node_index % 4 == 3 # right neighbor
      node.neighbors << @board[node_index - 1] unless node_index % 4 == 0 #left neighbor
      node.neighbors << @board[node_index + 4] unless node_index > 11 #bottom neighbor
      node.neighbors << @board[node_index - 4] unless node_index < 4 #top neighbor etc...
      node.neighbors << @board[node_index - 3] unless (node_index % 4 == 3) || (node_index < 4) #top right
      node.neighbors << @board[node_index + 3] unless (node_index % 4 == 0) || (node_index > 11) # bottom left
      node.neighbors << @board[node_index + 5] unless (node_index % 4 == 3) || (node_index > 11) # bottom right
      node.neighbors << @board[node_index - 5] unless (node_index % 4 == 0) || (node_index < 4) # top left
    end
  end

  # Traverse possible paths that may match the user's input.
  def include?(string, root = nil, used = [])
    string.upcase!
    used == [] ? paths = @board : paths = root.neighbors
    paths.each do |node| # First time look at the entire board. Next time node children.
      if (node.value == string[0]) && !used.include?(node)
        used << node
        return true if string == node.value # Base Case
        return include?(string[1..-1], node, used) # Recursion
      end
      used = []
    end

    return false

  end

end


class Node

  attr_accessor :neighbors, :value

  def initialize(letter)
    @value = letter
    @neighbors = []
  end

end

OurBoard = BoggleBoard.new()  
OurBoard.shake!

puts "==============================="

end_program = ""  
until end_program == "quit"  
  puts "please enter a string to search for"
  end_program = gets.chomp!
  if OurBoard.include?(end_program) == true
    p true
  else
    return end_program
  end
end  
Show Comments