A code along lesson plan for recursion

intro_to_recursion.rb

############### NOTES #####################
# Loops
#   -iterative
#   -recursive

# What is recursion?
#   -Another way to repeat instructions
#   -Instead of using built in looping methods, you simply repeat a method by calling itself
#   -The CS definition is that recursion solves a problem based on solutions to smaller problems, which differs from iteration in that iteration repeats a sequence of instructions a given number of times. Their outcomes are the same.

#   Notes on recursion
#   -Anything you can do with iteration, you can do with recursion, and anything you can do with recursion, you can do with iteration
#   -Recursion looks elegant and is good at subdividing tasks. Plays nicely with data structures like binary search trees or algorithms like merge sort. 
#   -Iteration is easier to conceptualize and is usually faster. Fits well when you know how many iterations you need. Counting over the length of an array, for example.
#   -When to use one or the other is partly a philosophical debate, but if you’re worried about speed, err towards iteration because it is usually faster, depending on the language and implementation because calling a method uses more system resources than iterating via built in methods. 
#   -It has somewhat of a mystical reputation because it’s not the looping structure most people learn initially, and it requires a bit more understanding than the built in enumerators.
#   -Its limited by memory concerns, too 

# Some nice slides about recursion
# http://www.cs.cornell.edu/info/courses/spring-98/cs211/lecturenotes/07-recursion.pdf

################ FAMILIAR ITERATIVE LOOPS #####################

10.times do |i|
  puts "#{i} from a times loop"
end

[1,2,3,4,5,6,7,8,9,10].each do |i|
  puts "#{i} from an each loop"
end

i = 0

while i < 10
  i += 1
  puts "#{i} from a while loop"
end

############### A RECURSIVE METHOD THAT DOES THE SAME THING #########
def recurse i = 0
  puts "#{i} from a recursion loop"
  unless i > 9
    recurse(i + 1)
  end
end

recurse 

########## WHERE IT GETS WEIRD ############

# It gets a little more confusing when you're trying to retain values. For example, if you wanted to populate an array, this is how you would do it iteratively.

arr = []

10.times do |i|
  arr << i
end

p arr

# So you might think the following code would work too

arr = []

def recurse i
  arr << i
  recurse i + 1 unless i > 9  # This is single line syntax for conditionals. It's the same as:
                              # unless i > 9
                              #   recurse i + 1
                              # end
end

recurse 0

# But it doesn't. You'll get an error because arr isn't in the method scope (It's not a local variable). So maybe you try something like

def recurse i
  arr = []
  arr << i
  p arr # just to show what's happening
  recurse i + 1 unless i > 9
end

recurse 0

# No errors, but it's simply creating a new array with a single value each time. Try this.

def recurse i, arr = []
  arr << i
  p arr
  recurse i + 1, arr unless i > 9
end

recurse 0

### TAKEAWAY ###
# To hold onto values in recursion, pass them as arguments to the method.

############### EXAMPLES ########################

#ITERATIVE solution to .prime?
def prime?(number) 
  # Create a loop that tests every number from 2 to number - 1
  (2..number - 1).each do |i| # test every num from 2 to 1 less than the number
    if number % i == 0 # if the given number is ever divisible by the check_num, it's not prime
      return false # this will end the method and return false
    end
  end

  true # if this line is executed, it means the number was never proven to be not prime, so we can say its prime
end

#RECURSIVE solution
def prime_recurse number, check_num = 2
  if check_num = number # we know we've checked every number from 2 to the number
    return true
  else
    return false if number % check_num == 0 
    prime_recurse(number, check_num + 1) # recursive call with the next check_num
  end
end

puts prime_recurse 15


############# THE RECURSIVE MODEL #############

# A lot of recursion examples will follow a familiar pattern. It's basically:

# method to do
  # if the base case is not met, 
    # do this code
  # if it is met,
    # return this value
#

# What's a base case you ask? It's the condition that must occur to exit a loop.

#In a times loop, it's the number that calls times. In an each loop, it's the length of the array. In a while loop, it's whenever the expression provided evaluates to false. It's less explicit in recursion, and we have to be more careful in establishing it. 

def recurse i = 1
  if i < 11 # base case is when i is not less than 11
    puts i
    i += 1
    recurse i
  else
    return i # and this code is executed, and it never recurses again
  end
end

recurse

#### THERE CAN BE MULTIPLE BASE CASES ####
# Look back at the prime_recurse method, and you'll notice there are two conditions for the recursion to end (Which is the same as saying for the loop to stop). Condition 1, we prove the number is not a prime. Condition 2, we prove the number is a prime. 

############## RECURSIVE CHALLENGE ################
# Write a program that returns the value of the Fibonacci sequence at a given position. The Fibonacci sequence is formed by adding the last two values in the sequence to form the next one. The first 7 values would be: 1, 1, 2, 3, 5, 8, 13. So, your method should work sorta like....

# recursive_fibonacci(7)
# => 13

# Scroll down for one of many possible solutions
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
def recursive_fibonacci index, i = 1, prev_num = 0, next_num = 1
  if i == index
    return next_num
  else
    recursive_fibonacci index, i + 1, next_num, prev_num + next_num
  end
end

recursive_fibonacci 7


########### MERGE SORT #################
# This is my implementation of merge_sort if you're curious. It's a good example of a more practical use of recursion.
class MergeSort
  def sort unsorted

    unless unsorted.size == 1
      half = unsorted.size / 2
      left = sort(unsorted[0...half])
      right = sort(unsorted[half..-1])
      merged = merge(left, right)
    else #basecase, when unsorted is one element long
      return unsorted
    end

  end

  def merge (left, right)
    
    merged = []

    while left.size > 0 && right.size > 0
      merged << (left.first < right.first ? left.shift : right.shift)
    end

    merged += left + right # One of these has to be empty, so just add both to get remainder
  end
end

merger = MergeSort.new
merger.sort[1,5,3,9]

###### END OF MY KNOWLEDGE ########