Fibonacci domino tiling There's classic combinatorial result that the number of ways to tile a 2*n strip by 1*2 dominoes is the nth Fibonacci number. You goal is to print all the tilings for a given n, drawn with dashes and vertical lines like these 8 tilings for n=5:

|————
|————

——|——
——|——

|||——
|||——

————|
————|

||——|
||——|

|——||
|——||

——|||
——|||

|||||
|||||


You are to provide a program or named function that take n as input and prints the required output. Fewest bytes wins.

Input

A number n between 1 and 10 inclusive via STDIN or function input.

Output

Print every possible domino tilings of the 2*n strip, drawn horizontally. The tilings may be in any order, but each should appear exactly once. They must be separated by a blank line.

A vertical domino is made of two vertical bars (|) and a horizontal domino is made of two em dashes (—). You may use hyphens (-) in place of em dashes to stay in ASCII.

You can do anything with whitespace as long as the printed output looks the same.
C, 106
Golfed version
f(n){
  for(int i,h=n*2&lt;&lt;n;h--;(i/3|i/3*2)-i||(putchar(i&gt;&gt;h%n&amp;1?45:124),h%n||puts(h%(n*2)?&quot;&quot;:&quot;\n&quot;)))
    i=h/2/n;
}

Original version
i,j,n;
main(){
  scanf(&quot;%d&quot;,&amp;n);
  for(i=1&lt;&lt;n;i--;)if((i/3|i/3*2)==i){
    for(j=1&lt;&lt;n;j/=2;)printf(&quot;%c&quot;,i&amp;j?'-':'|');puts(&quot;&quot;);
    for(j=1&lt;&lt;n;j/=2;)printf(&quot;%c&quot;,i&amp;j?'-':'|');puts(&quot;\n&quot;);
  }
}

How it works
The variable i runs from 1&lt;&lt;n-1 down to 0, producing all possible binary numbers with n digits. 0 encodes for | and 1 encodes for -. We are interested in numbers that contain 1's in pairs. Obviously such numbers are divisible by 3.
When a number is divided by 3, the original number can be recovered by multiplying the result by 2 and adding it to itself (effectively mutliplying by 3.) Most numbers will require a carry, but when the process is carried out on the numbers of interest, no carry is required, so in these cases only, OR can be used instead of addition. This is used to test for the numbers of interest, as they are the only ones where the expression i/3|i/3*2 returns the original value of i. See example below.
1111=15 ---&gt; 0101=5 ---&gt; 1111=15 (valid, 0101|1010==0101+1010)
1001=9  ---&gt; 0011=3 ---&gt; 0111=7 (invalid, 0011|0110 != 0011+0110)
The test value is always equal or less than the original value. As numbers that are not multiples of 3 also return a number less than the original when divided by 3 then multipled by 3, the test gives the desired FALSE on these numbers too.
In the original version a couple of loops in j are used to scan through the bits of i and produce the output. In the golfed version a single for loop is used, in which h runs through all numbers from (n*2)*(1&lt;&lt;n)-1 down to 0. Values of i are generated by h/2/n. The variable j is no longer used, as the equivalent quantity is obtained from h%n. The use of n*2 enables both lines to be printed from the same loop, with some nifty multiplexing in the puts statement to print either one or two newlines at the end of the row.
Note that the meat of this is in the increment position of the for() bracket and therefore gets executed after the i=h/2/h.
Sample output n=6:
$ ./a
6
------
------

----||
----||

--|--|
--|--|

--||--
--||--

--||||
--||||

|----|
|----|

|--|--
|--|--

|--|||
|--|||

||----
||----

||--||
||--||

|||--|
|||--|

||||--
||||--

||||||
||||||