recursion method inside ruby minesweeper game stack level too deep

Question

I am triggering endless recursion when trying to make a method that pulls up tiles when they are a zero. I have been testing by entering the following in irb:

class Board
  attr_accessor :size, :board

  def initialize(size = gets.chomp.to_i)
    @size = size
    @board = (1..@size).map { |x| ["L"] * @size }
  end

  def print_board
    @board.map { |row| puts row.join }
  end
end

class Mine
  attr_accessor :proxi, :row, :col

  def initialize(proxi)
    @proxi = proxi
    @row = 0
    @col = 0
    @random = Random.new
    check_position
  end

  def check_position
    if @proxi.board[@row - 1][@col - 1] != "L"
      @row = @random.rand(1..@proxi.board.length)
      @col = @random.rand(1..@proxi.board[0].length)
      check_position
    else
      map_position
    end
  end

  def map_position
    @proxi.board[@row - 1][@col - 1] = "*"
  end
end

b = Board.new(20)
m = (1..b.size * 2).map { |i| i = Mine.new(b) }

class Detector
  attr_accessor :board, :proxi, :row, :col, :value

  def initialize(board, proxi)
    @board = board
    @proxi = proxi
    @row = 0
    @col = 0
    @value = 0
  end

  def mine?
    if @proxi.board[@row - 1][@col - 1] == "*"
      true
    else
      false
    end
  end

  def detect
    (@row - 1..@row + 1).each do |r|
      (@col - 1..@col + 1).each do |c|
        unless (r - 1 < 0 || r - 1 > @proxi.size - 1) || (c - 1 < 0 || c - 1 > @proxi.size - 1)
          @value += 1 if @proxi.board[r - 1][c - 1] == "*"
        end
      end
    end
  end

  def map_position
    @proxi.board[@row - 1][@col - 1] = @value
    @board.board[@row - 1][@col - 1] = @value
  end

  def recursion
    if @proxi.board[@row - 1][@col - 1] == 0
      (@row - 1..@row + 1).each do |r|
        (@col - 1..@col + 1).each do |c|
          unless (r - 1 < 0 || r - 1 > @proxi.size - 1) || (c - 1 < 0 || c - 1 > @proxi.size - 1)
            @row, @col = r, c 
            detect
            map_position
            recursion
          end
        end
      end
    end
  end

  def reset
    @row, @col, @value = 0, 0, 0
  end
end

d = Detector.new(b, b)
b.print_board

If the output has plenty of free space in the upper right corner proceed to pasting the next part, else repaste.

d.row = 1
d.col = 1
d.mine?
d.detect
d.map_position
d.recursion
b.print_board

It will error out with a stack level too deep error at the recursion method. I know this is because it is having issues ending the recursive pattern. I thought my two unless statements deterring it from searching off the board would limit it to the area in the board. Plus the mines would force it to be limited in zeros it can expose. Maybe it is somehow writing spaces off the board or overwriting things on the board?

Answer 1

Exceeding the stack size is usually an indication that your recursion does not have the correct terminating condition. In your case, what mechanism is in place to prevent recursion from being called multiple times with the same @row @col pair? Note that of the 9 pairs that (@row - 1..@row + 1) (@col - 1..@col + 1) produce, one of those pairs is @row @col itself. The function will call itself infinitely many times!

A simple way to solve this would be to have something like a revealed array that keeps track of visited cells. Then recursion would mark each cell it visits as visited and return immediately if it is called on an already visited cell.

Additionally, your use of instance variables is extremely fragile here. Recursion relies on the fact that each function call has its own scope, but every call of recursion shares the same instance variables - which you're using to pass arguments! You should be using method arguments to keep the scopes distinct.

Answer 2

You don’t need a recursion here. Simply check each position for mines around:

Please always use 0-based arrays to eliminate lots of @blah - 1.

In detect you need to return immediately if there is a mine and set the @value otherwise:

def detect
  return if @proxi.board[@row][@col] == '*'
  value = 0 # no need to be global anymore
  (@row - 1..@row + 1).each do |r| 
    (@col - 1..@col + 1).each do |c| 
      unless r < 0 || r >= @proxi.size || c < 0 || c >= @proxi.size
        value += 1 if @proxi.board[r][c] == "*" 
      end
    end 
  end
  @proxi.board[@row][@col] = value
end 

Now you don’t need map_position method at all. Simply check all the cells:

def check
  (0..@proxi.size - 1).each do |r|
    (0..@proxi.size - 1).each do |c|
      @row, @col = r, c
      detect
    end
  end
end

Hope it helps.