Day 4 of 30 - Ruby Coding Challenge - Prime Algorithm Recursively

Hey!

Day 4 of 30: Ruby Coding Challenge number 4. This is the post version of the Youtube video.

I want to rewrite the coding challenge number 3 using recursion, which was:

How many prime items are in a given array?

Let’s get into it.

#1 - First Algorithm Version

It was the final algorithm version:

xxxxxxxxxx

def count_prime_number_version_2(array)

  array.count do |item|

    is_prime_number(item)

  end

end

def is_prime_number(item)

  return false if item == 1

  (2..(item - 1)).each do |number|

    if item % number == 0

      return false

    end

  end

  return true

end

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

puts count_prime_number_recursively(array)

Instead of having that array loop in the is_prime_number() method:

xxxxxxxxxx

def is_prime_number(item)

  return false if item == 1

  (2..(item - 1)).each do |number|

    if item % number == 0

      return false

    end

  end

  return true

end

We’re going to rewrite this method using recursion.

#1 Recursive Algorithms

I know. Recursion is one of the monsters when it comes to coding, along with memory management and giving names to variables.

Just a quick reminder:

A recursive algorithm calls itself with a smaller version of its own problem

I’m not going to go into much detail about recursion because I’m kind of assuming you already know something about it, however, I might be wrong. Because of that, I’m recording and writing a special tutorial to go through the benefits (and some costs) of recursive algorithms.

Step 1:

A recursive function calls itself

xxxxxxxxxx

def is_prime_number(item)

  return is_prime_number(item)

end

Step 2:

We need at least one condition to call the function again, which is when item is not evenly dividable by number

xxxxxxxxxx

def is_prime_number(item)

  return is_prime_number(item) if item % number != 0

end

Step 3:

We already know that 1 is not a prime number, as we’ve seen in the previous algorithm.

xxxxxxxxxx

def is_prime_number(item)

    return false if item == 1

  return is_prime_number(item) if item % number != 0

end

Step 4:

We should call the method itself with the current number - 1, which is the logic we have using so far

xxxxxxxxxx

def is_prime_number(item, number)

    return false if item == 1

  return is_prime_number(item, number - 1) if item % number != 0

end

Step 5:

We should return true if number reaches 1, which means that the number is actual prime

xxxxxxxxxx

def is_prime_number(item, number)

    return false if item == 1

    return true if number == 1

  return is_prime_number(item, number - 1) if item % number != 0

end

The entire code is:

def count_prime_numbers(array)

  array.count do |item|

    is_prime_number(item, item - 1)

  end

end

def is_prime_number(item, number)

    return false if item == 1

    return true if number == 1

  return is_prime_number(item, number - 1) if item % number != 0

end

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

puts count_prime_numbers(array)

And that’s it!

To be honest, this is not an easy topic (at least for me) to explain in writing and maybe you get a better picture watching the video :)

Just a reminder. This is not about Ruby; it’s all about concepts and logics and having some fun while solving these problems.

Thanks for your visit, let’s keep in touch and see you in the next challenge :)

Twitter Youtube Instagram Linkedin