 # Recursion: An Example in Ruby

written in

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:

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:

It just keeps going:

…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.

## 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.

## 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.