Recursion basics

Why learn recursion?

1) It's bad ass.
2) Many people view recursion as an acid test for how well an individual understands computer programming.
Know recursion well enough to reach for it in a technical interview (not super hard don't worry)?

#Hired.

3) It's fun and is guaranteed to give you a smug sense of superiority over people that haven't taken the time to practice
it yet. Oh, and the recursive code you write will be ridiculously clean.


So what is recursion?

Before diving in to what it is let's talk about when you might want to use it.

You've heard of loops like:

each
while
for
etc.

Recursion solves the same problems as loops/iterators => iterator means to iterate through a collection.

Fun fact, some functional programming languages DO NOT have looping iterators because they use recursion instead.


A more technical definition (that you could say in interviews) is: when a method calls itself.


Free classic book:
https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 (just do a search for recursion and read the chapters.
Super short and accessible).


BASIC RECURSION EXAMPLE

Countdown from 9 to 0
So the output we are lookin for is:

9, 8, 7, 6, 5, 4, 3, 2, 1, 0

We could use a simple built in loop like:

10.times do |num|
  9 - num
end


With recursion it looks like so:

def countdown(num)
  return num if num < 0
  num
  countdown(num - 1)
end

countdown(9)



Let's trace the stack to see what's happening.

countdown(9)
9, countdown(8)
9, 8, countdown(7)
9, 8, 7, countdown(6)
9, 8, 7, 6, countdown(5)
9, 8, 7, 6, 5, countdown(4)
9, 8, 7, 6, 5, 4, countdown(3)
9, 8, 7, 6, 5, 4, 3, countdown(2)
9, 8, 7, 6, 5, 4, 3, 2, countdown(1)
9, 8, 7, 6, 5, 4, 3, 2, 1, countdown(0)
9, 8, 7, 6, 5, 4, 3, 2, 1, 0


Practice time:

Split up into groups based on number of whiteboards.


Factorial => Remember factorial is a fancy math way of describing this pattern
7! => 7 * 6 * 5 * 4 * 3 * 2 * 1
2! => 2 * 1

GIVEN => 0! = 1




Via code:

class Factorial
  def self.calculate(number)
    return 1 if number == 0
    number * Factorial.calculate(number - 1)
  end
end

Factorial.calculate(5)


What does this look like from the recursive perspective?

DIVIDE AND CONQUER PATTERN

number = 5
5 * Factorial.calculate(5 - 1)
5 * Factorial.calculate(4) => Factorial.calculate(4) now get's called and the process repeats
5 * 4 * Factorial.calculate(4 - 1)
5 * 4 * 3 * Factorial.calculate(3 - 1)
5 * 4 * 3 * 2 * Factorial.calculate(2 - 1)
5 * 4 * 3 * 2 * 1 * Factorial.calculate(1 - 1) => Remember that 0! = 1 (they gave that to us).

5 * 4 * 3 * 2 * 1 * 1 = 120


The code is elegant. Crisp and clean. Now you are going to recreate it.

Recreate this from memory. Get as far as you can.


Studies have shown that two different sets of students given the same material to learn...
Group A: one session of looking at material and then self quiz trying to recall
Group B: multiple sessions of looking at material.

Group A greatly outperformed group B in recomposition a week/month/year later.


If you get stuck... Use these hints to try to get going. You will be better off than just rereading it several times (seriously).

Remember that in order for it to be a recursive method you need to have a few different things:

1) An iterator of some kind (in the example above we are using (n - 1)) to iterate down to 0 from n.
2) A way to escape once you reach the bottom of the stack (a "given" paremeter of some kind). In the example above we used "return 1 if number == 0



Next up we are going to work together to build the fibonacci method on the whiteboard.

Remember that the Fibonacci sequence is as follows.

GIVENS => number[0] = 0, number[1] => 1
...








class Fibonacci
  def calculate(number)
    return 0 if number == 0
    return 1 if number == 1
    Fibonacci.calculate(number - 1) + Fibonacci.calculate(number - 2)
  end
end

Fibonacci.calculate(5)

IDEAS for extra reaches =>

Spectrum at beginning to guage where people are at and help facilitate pairs down the road.
Don't use code.
Try to write it out and trace the stack.
Then write it out and teach a few things about pry as well? exit / whereami / ls