Recursion - Favorite Technical Concept from Mod 1

One of the hardest and most fun concepts I learned during mod 1 was ‘recursion’. This at times can feel like something out of the movie Inception, but it was one of the most powerful tools I learned. It allows you to loop over a part of your program until a condition is met. Each new layer puts a temporary pause on the layer that spawned it and then ruby cycles back up through the layers completing the remaining program at each level before returning to the level that spawned it.

source

Here is an example of a recursive method used to implement the Sieve of Eratosthenes to find prime numbers:

class Sieve
  def initialize(limit)
    @range = (2..limit).to_a
  end

  def primes(start = 2)
    return @range if @range.empty?
    @range.delete_if do |number|
      number != start && number % start == 0
    end
    if start != @range.last
      start = @range[@range.index(start)+1]
      primes(start)
    end
    @range
  end
end

Sieve.new(10).primes
# => [2, 3, 5, 7]

This creates an array of every number from 2 to the limit (in this case 10) then removes the ones that are multiples of that one then moves on to the next one. The method calls itself (primes(start)) with a new starting point in the array until we reach the last number in the array (if start != @range.last). If we were to look at the @range array through each step we would see:

[2,3,4,5,6,7,8,9,10] # initialize
[2,3,5,7,9] # first run through primes
[2,3,5,7] # recursion 1 - now start = 3
[2,3,5,7] # recursion 2 - now start = 5
[2,3,5,7] # recursion 3 - now start = 7

as it cycled through each level. However if we insert a p @range after the if start != @range.last ... end (which contains our recursion point) is called we would see the following output in the terminal:

[2, 3, 5, 7] # recursion 3's print
[2, 3, 5, 7] # recursion 2's print
[2, 3, 5, 7] # recursion 1's print
[2, 3, 5, 7] # first run's print

Each time ruby hits the primes(start) line we “drop down to a new level of the dream world” (a la Inception). On that level we execute the primes method from the start and if we hit primes(start) again, we drop to a level deeper. We keep doing this until primes returns (i.e. until it hits @range on the last line). This returns @range back to the previous level which then runs through the rest of its method (in this example printing @range to the terminal). It does this for each level until it returns back to the highest level and the program concludes.

Recursion can be very useful for avoiding while or until loops as well as dealing with smart node navigation (see “Smart Nodes all the time!” for a perspective on smart nodes).

Mod 1 – a test of character

I must admit, I had my doubts if Turing would be the right fit for me. I am a self-taught WordPress developer and had been successfully running my own web development company for years. I was worried that I might not get the most out of the program, because I already had a fair amount of coding knowledge. And yet, I was at a point where I wanted to dive deeper into coding and be immersed into a community of similar minded people. So I took the plunge.

Quickly it became clear, that I had to find my own way of succeeding at Turing. By that I don’t mean just getting the projects done on time but going further to be able to challenge myself and at the same time contribute to the community in the best way I can.

It’s a hard path and a difficult balance to strike. And I am grateful for the support I got from the instructors and the feedback from my cohort and other Turing students. Family and friends who know me well have commented that I look fulfilled and have rediscovered an intrinsic sense of motivation. I take that as a good reality check and as a confirmation that starting the program has so far been a good decision.

Most importantly though is the feeling that I am looking forward to starting Mod 2.