Recursion
For recursion in computer science, see recursive functions.
Recursion formalizes the process of recognizing how solutions to smaller cases of a problem can, layer by layer, be built up to solve any case of a problem, no matter how enormous. Needless to say, it can be tricky to figure out how to solve infinitely many problems simultaneously. That's what this wiki page will explain, so brace yourself for some problem solving that feels a bit loopy and oddly cyclic at times.
Contents
When to Use Recursion
Some signs that recursion might be a good method for attacking a problem are as follows:
- The problem asks for the value of a large case, and you can determine small values or they are given.
- There is a clear connection between small cases and large cases.
This example problem can be solved straight, without recursion. But the recursive solution is a beautiful and efficient approach.
How many red triangle tiles will be needed for the next \((\)the \(4^\text{th})\) layer of this star pattern?
There's no shame in solving this puzzle by counting (although doing so accurately might be trickier than you think). You might even come up with a clever way to count – say, by recognizing that each arm of the star will need the same number of triangles. But neither of these methods is as practical or as elegant as recursion.
If you're not convinced yet that a recursive method is worth the investment, consider counting all of the triangles in the \(1000^\text{th}\) level of this pattern. There are 23988 of them.
Why use recursion? Because no one would ever want to count that high! Using recursion, you'll be able to solve this problem easily by the end of the next section.
Recursive Problem Solving
Recursion should be applied as a technique when the problem you're solving is like an onion. Using recursion requires realizing that a big, complex problem that's likely to make you cry is really just a slightly smaller problem, plus one super-thin layer. And that problem, in turn, is just a slightly smaller problem, plus one super-thin layer...
Steps of Recursive Problem Solving
Create and analyze smaller cases of the problem.
Try to construct larger cases using smaller cases.
Make a conjecture (a guess) about how small cases are generally related to larger cases.
Prove your conjecture and translate it into a general formula that uses the answers to smaller/simpler cases of the problem to find the answer to a larger/more difficult case.
Use the formula from step 4 to build up to the solution to the specific layer you care about.
Critically, in step 4, the relationship between smaller and larger cases needs to be a general one for constructing any case of the problem from earlier/smaller cases, not just a single example of making a specific complex case from specific earlier cases.
These steps are the secret to efficiently and beautifully solving many problems that would make the average Joe weep.
How many red triangle tiles will be needed for the next (the 4th) layer of this star pattern?
We will solve this problem using recursion. Thinking recursively solves this problem beautifully and efficiently.
Step 1 Create and analyze smaller cases of the problem.
The natural cases in this problem are the sequential layers of the star:
- The first layer has 12 triangles.
- The second layer has 36 triangles.
- The third layer has 60 triangles.
Step 2 Try to construct larger cases using smaller cases.
Compare the \(1^\text{st}\) layer to the \(2^\text{nd}\) layer, and the \(2^\text{nd}\) layer to the \(3^\text{rd}\) layer:
Step 3 Make a conjecture (a guess) about how small cases are generally related to larger cases.
Notice that by moving groups of the triangles in one layer away from the center and then adding 24 extra triangles in diamond-shaped pairs, we can make the next layer of the pattern from each previous layer.
This geometric relationship between two sequential layers is a general one that works for any two sequential layers.
Step 4 Prove your conjecture and translate it into a general formula that uses the answers to smaller/simpler cases of the problem to find the answer to a larger/more difficult case.
Each layer will require 24 more triangles than the layer just before it!
If \(C_n\) is the answer to case \(n\) of the problem, then \(C_n = C_{n-1} + 24\) and \(C_1\) = 12 since with one layer, there are 12 triangles in the star.
Step 5 Use the formula from step 4 to build up to the solution to the specific layer you care about.
Finding the number of triangles in the \(4^\text{th}\) layer:
- Case 1: There are 12 triangles in the initial star.
- Case 2: There are \(12 + 24 = 36\) triangles in the \(2^\text{nd}\) layer.
- Case 3: There are \(36 + 24 = 60\) triangles in the \(3^\text{rd}\) layer.
- Case 4: There are \(60 + 24 = \boxed{84}\) triangles in the \(4^\text{th}\) layer. \(_\square\)
Too big for counting? Definitely. Too big for recursion? Never!
Patterns with a Longer Memory
Finding a recurrence relation requires identifying some regular relationship between each case of a problem and the earlier cases. But many times it won't be solely the case just before that's relevant. Sometimes, later cases will evolve from combining two, three, or any number of previous cases together.
You're creating a catalog of tile designs for a friend. In this series of designs, the area to be tiled is 2'' x 16'' and the tiles are each 1'' x 2''. How many different ways are there to cover the area with tiles?
A few examples:
Step 1 Create and analyze smaller cases of the problem.
The length of the area can be decreased in order to make this problem simpler. It is definitely easier to count how many ways a 2'' x 5'' rectangle could be tiled for example. Additionally, our wishful thinking at this stage is that somehow the solution to the 2'' x 16'' case would be easy to figure out if only we knew the solution to the 2'' x 15'' case already...The sequence of problems this reasoning suggests is to consider tiling a 2'' x 1'' area, then a 2'' x 2'' area, then a 2'' x 3'' area, etc. Therefore, the general case is 2'' x n''.
Solving the Smallest Cases
\(C_1=1\)
There is 1 way to tile a 1'' x 2'' area.
\(C_2=2\)
There are 2 ways to tile a 2'' x 2'' area.
\(C_3=3\)
There are 3 ways to tile a 3'' x 2'' area.
\(C_4=5\)
There are 5 ways to tile a 4'' x 2'' area.
Step 2 Try to construct larger cases using smaller cases.
We could keep doing out cases one at a time or, at any point, we can start looking for a pattern. Try using the sets above as a tool to identify all of the tiling patterns for \(C_5\). How can you make a larger tile pattern out of a smaller one?
Step 3 Make a conjecture (a guess) about how small cases are generally related to larger cases.
Say, for example, that we're trying to figure out the number of tiling patterns for \(n = 5\), aka, the number of ways to tile a 5'' x 2'' area with dominoes. To start, we know that there are at least 5 ways to do it: take each of the five \(n = 4\) solutions and add one new vertical tile on the left:
But are there more solutions? Yes. Above are all of the solutions that start with one vertical tile, but what about all of the solutions that start with two horizontal tiles on the far left?
If there are 3 inches left to fill after these two tiles on the left, how many ways are there to fill these 3 inches? \(C_3 = 3.\)
Step 4 Prove your conjecture and translate it into a general formula that uses the answers to smaller/simpler cases of the problem to find the answer to a larger/more difficult case.
Generalizing this observation, for any \(n\)'' x 2'' area, there are \(C_{n-1}\) tilings with one vertical domino on the far left, and \(C_{n-2}\) tilings with two horizontal dominoes on the far left. So \(C_n = C_{n-1} + C_{n-2}\). In words, the solution to each case is the sum of the solution to the two previous cases.
That's the Fibonacci sequence! Apart for the base case terms which are, in this case, \(C_1 = 1\) and \(C_2 = 2\).
Step 5 Use the formula from step 4 to build up to the solution to the specific layer you care about.
You're creating a catalog of tile designs for a friend. In this series of designs, the area to be tiled is 2'' x 16'' and the tiles are each 1'' x 2''.
How many different ways are there to cover the area with tiles?
Note: The image shows a few examples that describe such scenario.
INFINITE Recursion!
At this point, stopping at any specific point in the recursion process might feel kind of arbitrary--why get off at the \(1001^\text{st}\) floor of a building when you can take the elevator up to the moon... and beyond?
Whenever you define a recursive process, you can imagine taking the infinite limit of that process, asking, "What are we approaching as we repeat the process over and over and over again?" Sometimes, infinity does amazing things to recursion.
Fractals are a beautiful application of the infinite extension of recurrence relations. One particular kind of fractal called an iterated function system (IFS) is pretty much just visual recursion on an infinite kick. These fractals are made using recursive processes. Here are a few examples of IFS fractals:
Sierpinski's Triangle
1) Start with a right isosceles triangle of side length 1.
2) Draw lines connecting the centers of each edge and remove the inverted triangle that these edges form.
3) Draw lines connecting the centers of each edge of the remaining solid triangles. Remove the inverted triangles that these edges form.
... repeat step 3 process over and over again, each time removing smaller, inverted triangles from the center of each remaining triangle.
If step 3 is repeated infinitely many times...
Infinitely many. For example, imagine the left corner of the triangle at the origin of a graph and the left edge of the triangle as a vertical line from 0 to 1. In the first iteration of the process, the center point \(\frac12\) is removed, then \(\frac14\) and \(\frac34,\) then \(\frac18, \frac38, \frac58,\) and \(\frac78,...\) etc. But \(\frac13\) will never be removed, nor will \(\frac19, \frac1{27},...\) etc. In fact, on the vertical edge of the figure, even though infinitely many points are removed, more points remain in the fractal.
There will be no line segments left in the image. The vertical left edge of the final fractal looks like a line, but so many points have been removed from it that there are no continuous sections of line left. In other words, eventually, every line segment in the image has at least one point removed from it, breaking it. So the final 'length' of every segment will be 0.
None. For any patch of solid area that initially exists, eventually, some portion of it is removed by the recursive process. Therefore, no solid patches of area remain after executing the recursive process infinitely many times.
Conclusion: Fractals are weird!
Further Topics in Recursion
- Linear Recurrence Relations
- Finding Irregular Closed Form Solutions via the Substitution Method
(Converting a recursive pattern into a formula that immediately gives out an answer for any specific case, without needing to sequentially figure out every smaller solution.) - Finding the Closed Form of Recurrence Relations via the Master Theorem
- Even More about Recurrence Relations
- Generating Functions - Solving Recurrence Relations
- The Y-Combinator (Lambda Calculus)