Day 4 of 30 - Ruby Coding Challenge - Prime Algorithm Recursively
Day 4 of 30 - Ruby Coding Challenges in 30 Days. I want to rewrite the previous coding challenge using recursion, which was counting how many items are in a given array
Join the DZone community and get the full member experience.
Join For FreeHey!
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 :)
Published at DZone with permission of Alexandre Gama. See the original article here.
Opinions expressed by DZone contributors are their own.
Trending
-
A Data-Driven Approach to Application Modernization
-
Auto-Scaling Kinesis Data Streams Applications on Kubernetes
-
Managing Data Residency, the Demo
-
What I Learned From Crawling 100+ Websites
Comments