Search code examples
rubyrecursioncoin-flipping

Simple recursion problem

I'm taking my first steps into recursion and dynamic programming and have a question about forming subproblems to model the recursion.

Problem:

How many different ways are there to flip a fair coin 5 times and not have three or more heads in a row?

If some could put up some heavily commented code (Ruby preferred but not essential) to help me get there. I am not a student if that matters, this is a modification of a Project Euler problem to make it very simple for me to grasp. I just need to get the hang of writing recursion formulas.

If you would like to abstract the problem into how many different ways are there to flip a fair coin Y times and not have Z or more heads in a row, that may be beneficial as well. Thanks again, this website rocks.

Solution

  • Here's my solution in Ruby

    def combination(length=5)
  return [[]] if length == 0
  combination(length-1).collect {|c| [:h] + c if c[0..1]!= [:h,:h]}.compact +
  combination(length-1).collect {|c| [:t] + c }
end

puts "There are #{combination.length} ways"

    All recursive methods start with an early out for the end case.

    return [[]] if length == 0

    This returns an array of combinations, where the only combination of zero length is []

    The next bit (simplified) is...

    combination(length-1).collect {|c| [:h] + c } +
combination(length-1).collect {|c| [:t] + c }

    So.. this says.. I want all combinations that are one shorter than the desired length with a :head added to each of them... plus all the combinations that are one shorter with a tail added to them.

    The way to think about recursion is.. "assuming I had a method to do the n-1 case.. what would I have to add to make it cover the n case". To me it feels like proof by induction.

    This code would generate all combinations of heads and tails up to the given length.

    We don't want ones that have :h :h :h. That can only happen where we have :h :h and we are adding a :h. So... I put an if c[0..1] != [:h,:h] on the adding of the :h so it will return nil instead of an array when it was about to make an invalid combination.

    I then had to compact the result to ignore all results that are just nil