To Understand Recursion

DRAFT WIP - TODO

...you must first understand recursion. Recursion is the idea that you can have a function call itself to break a problem down into smaller pieces. Sound odd? Well buckle up because this is going to be a trip.

( This is probably going to be another heavily illustrated chapter as recursion the first time can be hard to grok )

Breaking it down

( Definitely going to want to rewrite this later )

Remember Factorial from Math class? Five factorial, for instance, would look like this: 5!.

Just as a refresher, what that translates to is: 5 * 4 * 3 * 2 * 1.

So how does that apply to recursion? Well, would you say it's fair that 5! could be expressed as 5 * 4!? Could 4! be expressed as 4 * 3!?

We don't know what 5! is, but we know it's 5 multiplied by the factorial of the next lowest number. In Ruby that might look like this:

factorial(5)
5 * factorial(4)

The question is if there's a base case we know is true. With factorial, we know that 1! is just 1:

factorial(5)
5 * factorial(4)
5 * 4 * factorial(3)
5 * 4 * 3 * factorial(2)
5 * 4 * 3 * 2 * factorial(1)
5 * 4 * 3 * 2 * 1

Written in Ruby that would look like:

def factorial(n)
  return 1 if n == 1

  n * factorial(n - 1)
end

We use a guard statement for our base case, and if it's not we just keep multiplying n by the factorial of one less than n until we hit 1.

As soon as it finally hits that base case we know what all the other steps are and the function gets the values it needs to complete that it was waiting on.

Don't forget that base case though, or you'll end up doing the same thing infinitely. In the case of Ruby, it would eventually stop when it hits a "Stack too deep" error. Turns out for really big problems Ruby doesn't work well with recursion like some other languages.

Where's the Map?

( Need better title headers in here )

( Implementing map recursively )

Select

( Implementing select recursively )

Reduce

( Implementing reduce recursively )