Skip to content

Instantly share code, notes, and snippets.

@samlandfried
Created April 20, 2017 21:52
Show Gist options
  • Save samlandfried/9ca8d56d487a067f8fddf20878e220b0 to your computer and use it in GitHub Desktop.
Save samlandfried/9ca8d56d487a067f8fddf20878e220b0 to your computer and use it in GitHub Desktop.
A code along lesson plan for recursion
############### 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 ########
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment