Recursion: An Example in Ruby
Recursion is most commonly defined as “a process wherein a method can call themselves until they reach a goal.”
We say that a method is “recursive” if it
 Has an end goal, or base case
 Uses a process in which the task at hand is reduced towards that end goal
Divide and Conquer
Recursion is useful as a way to divide a large problem into a smaller one. The most common way to explain recursion is to use it to calculate the factorial of a number. A factorial is the product of all positive integers less than or equal to the number. Therefor, the factorial of 5 is equal to 12345.
For example:
1 2 3 4 5 6 7 8 9 

This method returns the factorial of a number by first checking to see if the number is negative. If the number is positive, and is greater than 1, we multiply that number times the factorial of the number immediately preceding it. We could represent this (in pseudo code) as:
1 2 

In this example, you can see that now we’re calling factorial(4)
, so we add this to the stack, and we get:
1 2 3 

It just keeps going:
1 2 3 4 5 

…until we get to the condition where we would no longer call factorial
— when we ask for the factorial of 1, which is 1. At that point, we’ve hit the end, and we begin to return values for each call to the method.
1 2 3 4 5 

Why is this better than a loop?
Often its not. If you find yourself saying “Geez, I wish I’d used a loop here” then you probably should. Sometimes, though, recursion is the best tool to use, and its the sort of solution that is worth learning, at least conceptually.
Links
 A King And His Rocks
 Ruby Recursion [VIDEO]
 Flood Fill, Zombies, and Kittens
 Fibonacci
 CodeQuiz on Recursion
Projects
(from The Odin Project)
Fibonnacci
The Fibonacci Sequence, which sums each number with the one before it, is a great example of a problem that can be solved recursively.
Your Task
 Write a method #fibs which takes a number and returns that many members of the fibonacci sequence. Use iteration for this solution.
 Now write another method #fibs_rec which solves the same problem recursively. This can be done in just 3 lines (or 1 if you’re crazy).
Coin Flips
How many different ways are there to flip a fair coin 5 times and not have three or more heads in a row? How about 10^{10} times and not have 534 or more heads in a row?