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.
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:
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.
- A King And His Rocks
- Ruby Recursion [VIDEO]
- Flood Fill, Zombies, and Kittens
- CodeQuiz on Recursion
(from The Odin Project)
The Fibonacci Sequence, which sums each number with the one before it, is a great example of a problem that can be solved recursively.
- 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).
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 1010 times and not have 534 or more heads in a row?