Bit-Reversal Permutations

Haskell, 40 37 bytes

f 0=[0]
f a=[(*2),(+1).(*2)]<*>f(a-1)

Try it online!

Thanks to @Laikoni for three bytes!


05AB1E, 8 bytes

Code:

¾)IF·D>«

Explanation:

¾         # Constant for 0.
 )        # Wrap it up into an array.
  IF      # Do the following input times.
    ·     # Double every element.
     D    # Duplicate it.
      >   # Increment by 1.
       «  # Concatenate the first array.

Uses the CP-1252 encoding. Try it online!.


J, 15 11 bytes

2&(*,1+*)0:

There is an alternative for 15 bytes that uses straight-forward binary conversion and reversal.

2|."1&.#:@i.@^]

Usage

   f =: 2&(*,1+*)0:
   f 0
0
   f 1
0 1
   f 2
0 2 1 3
   f 3
0 4 2 6 1 5 3 7
   f 4
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

Explanation

2&(*,1+*)0:  Input: n
         0:  The constant 0
2&(     )    Repeat n times starting with x = [0]
2      *       Multiply each in x by 2
     1+        Add 1 to each
    ,          Append that to
2  *           The list formed by multiplying each in x by 2
               Return that as the next value of x
             Return the final value of x